````

求两个数相乘之后的平方数个数

#include <iostream>

#include <cstdio> #include <cstring> #include <queue> #include <vector> #include <algorithm> using namespace std; #define cl(A,b) memset(A,b,sizeof A); const int maxn = 1000000+ 2; int a[maxn],vis[maxn],prime[maxn]; vector<int>ve; void init() {     for( int i = 2; i < 1005; i++ ){         if(!prime[i]){             for( int j = i*i; j < 1005; j += i ){                 prime[j] = 1;             }         }     }     for( int i = 2; i < 1005; i++ ){         if(!prime[i]){ve.push_back(i*i);}     }     //cout<<ve.size()<<endl; } int main() {     init();     int T;scanf("%d",&T);     while(T--){         int n;scanf("%d",&n);         cl(vis,0);         for( int i = 0; i < n; i++ ){             scanf("%d",a+i);             for( int j = 0; a[i] >= ve[j] && j < ve.size(); j++ ){                 while(a[i] % ve[j] == 0){                     a[i] /= ve[j];                 }             }             vis[a[i]]++;         }         int ans = 0;         for( int i = 1; i <= 1000000; i++ )             ans += vis[i]*(vis[i]-1)/2;         printf("%d\n",ans);     }     return 0;

}

http://blog.csdn.net/jnxxhzz/article/details/60969370