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.
“浪潮杯”山东省第六届ACM大学生程序设计竞赛
题解：
类似上一题。唯一分解定理。保留原始值和匹配值。之后求组合数
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6+10; bool isprime[1100]; vector<int> primes; void mk_Prime() { memset(isprime,true,sizeof(isprime)); isprime[0] = isprime[1] = 0; for(int i=2;i<1100;i++) { if(isprime[i]) primes.push_back(i); for(int j=0;j<(int)primes.size() && i*primes[j] < 1100;i++) { isprime[i*primes[j]] = 1; if(i % primes[j] == 0) break; } } } map<ll,ll> ma,its; map<ll,ll> ::iterator it; ll get_Factor(ll x) { ll ans1 = 1; ll ans2 = 1; for(int i = 0; i < (int)primes.size() && primes[i] * primes[i] <= x; i++) { int cnt = 0; while( x % primes[i] == 0) { x /= primes[i]; cnt++; } if(cnt % 3 == 1) { ans1 *= primes[i]; ans2 *= (primes[i]*primes[i]); } else if(cnt % 3 == 2) { ans1 *= (primes[i]*primes[i]); ans2 *= primes[i]; } } if(x > 1) { ans1 *= x; ans2 *= (x*x); } its[ans1] = ans2; return ans1; } int main() { mk_Prime(); int caset;scanf("%d",&caset); while(caset--) { ma.clear(); its.clear(); int n;scanf("%d",&n); for(int i=0;i<n;i++) { ll x; scanf("%lld",&x); ma[get_Factor(x)]++; } ll ans = 0; for(it=ma.begin();it!=ma.end();it++) { if(it->first == 1) { ans += it->second * (it->second-1); } else { if(ma.count(its[it->first])) ans += it->second * ma[its[it->first]]; } } printf("%lld\n",ans/2); } return 0; }