In mathematics, a cube number is an integer that is the cube of an integer. In other words, it is the product of some integer with itself twice. For example, 27 is a cube number, since it can be written as 3 * 3 * 3.
Given an array of distinct integers (a1, a2, ..., an), you need to find the number of pairs (ai, aj) that satisfy (ai * aj) is a cube number.
The first line of the input contains an integer T (1 ≤ T ≤ 20) which means the number of test cases.
Then T lines follow, each line starts with a number N (1 ≤ N ≤ 100000), then N integers followed (all the integers are between 1 and 1000000).
For each test case, you should output the answer of each case.
先筛掉每个原数中的立方因子得到新数，对于每一个新数，若存在平方因子，则需要找该平方因子为1的对应的数与其匹配；若不存在平方因子（即只含单个因子），则找含有两个该单因子的数与其匹配。
注意，找到的匹配的数可能会超过1e^6，此时需要判断一下，并且用long long来存储，否则会RE。
具体代码实现的时候，使用一个变量tem，记录当前的数所含素因子的情况，即每次把当前的数所含的平方因子、单个因子都用tem累乘起来。该tem的个数加1。这样下一个数找对应匹配的数的时候，只要累加之前已经出现过的对应匹配的数的个数就可以了。
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; typedef long long ll; const int maxn = 1005; bool vis[maxn]; int prim[maxn], cnt[1000005], tol; void init()//1000以内的素数打表 { for(int i = 2; i <= 1000; i++) { if(!vis[i]) prim[tol++] = i; for(int j = 0; j < tol && prim[j]*i <= 1000; j++) { vis[i*prim[j]] = true; if(i % prim[j] == 0) break; } } } int main() { init(); int n, ans, T; cin >> T; while(T--) { cin >> n; ans = 0; memset(cnt, 0, sizeof(cnt)); for(int i = 1; i <= n; i++) { int x; bool flag = true; int self = 1;ll need = 1; cin >> x; for(int j = 0; j < tol && prim[j] <= x; j++) { int y = prim[j]*prim[j]*prim[j]; while(x%y == 0) x /= y; if(x%(prim[j]*prim[j]) == 0) { x /= (prim[j]*prim[j]); self = self * prim[j] * prim[j]; if(flag) need *= prim[j]; } else if(x%prim[j] == 0) { x /= prim[j]; self *= prim[j]; if(flag) need *= (prim[j]*prim[j]); } if(need > 1e6) flag = false; } if(flag) { if(x != 1) need = need*x*x;//这里不能用*=,因为x会爆int if(need <= 1e6) ans += cnt[need]; } if(x != 1) self *= x; cnt[self]++; } cout << ans << endl; } return 0; }
