fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 100004;
  4. using ll = long long;
  5. vector<int>spf;
  6. void spfA(){
  7. 	spf.resize(MAXN+1);
  8.  
  9. 	for(int i = 2 ; i<=MAXN ;i++){
  10. 		spf[i]=i;
  11. 	}
  12. 	//spf[0]=spf[1]=1;
  13. 	for(int i = 2;i*i<=MAXN;i++ ){
  14. 		if(spf[i] == i){
  15. 			for(int j = i*i;j<=MAXN ;j+=i){
  16. 				if(spf[j]==j){
  17. 					spf[j]=i;
  18. 				}
  19. 			}
  20. 		}
  21. 	}
  22. }
  23.  
  24. unordered_map<ll,ll>cl(ll v1){
  25. 	unordered_map<ll,ll>a2;
  26.  
  27. 	while(v1!=1){
  28. 		ll d = spf[v1];
  29. 		a2[d]++;
  30. 		v1=v1/d;
  31. 	}
  32. 	return a2;
  33. }
  34. int main() {
  35.     int n;
  36.     cin>>n;
  37.  
  38.     vector<int>a(n);
  39.     int count = 0;
  40.     spfA();
  41.     unordered_map<ll,ll>b2;
  42.     for(int i = 0;i < n ;i++){
  43.     	cin>>a[i];
  44.     	ll gg = 1;
  45.     	    unordered_map<ll,ll>a2 = cl(a[i]);
  46.     	    for(auto it : a2){
  47.     	    	if((it.second)%2 != 0){
  48.     	    		gg = gg*(it.first);
  49.     	    	}
  50.     	    }
  51.     	    count = count + b2[gg];
  52.     	    b2[gg]++;
  53.     }
  54.  
  55. cout<<count<<endl;
  56. 	return 0;
  57. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5
1 36 9 4 6
stdout
copy 
6
https://ideone.com/vZz16G
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!