Description
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.
Input
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).
Output
For each test case, you should output the answer of each case.
Sample Input
1 5 1 2 3 4 9Sample Output
2【分析】
题意：给定一串数字，求有多少对i,j满足a[i]*a[j]是一个立方数
跟另外一道题雷同，这道题是下一题的进阶版...
首先，先对每个数进行质因数分解，如果a[i]和a[j]满足条件
那么就是他们中某个质因子的个数和为3的倍数，所以与平方数一样，先去掉所有立方因子，因为立方因子不会对答案造成影响。
不过平方数是在之前的数中找自己，而立方数就是在之前的数中找那个能凑够因子数为3倍数的那个数，中途记录就可以了，还是一样笔算模拟一下就知道怎么找了...也算是经典题吧
【代码】
#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; int len=0; int vis[1100100]={0}; int prime[10000]={0}; void init() { for(int i=2;i<1010;i++) if(!vis[i]) { prime[len++]=i; for(int j=i+i;j<1010;j+=i) vis[j]=1; } } int main() { init(); long long x,t,temp,find; int n,ans; int pp;scanf("%d",&pp); while(pp--) { memset(vis,0,sizeof(vis)); scanf("%d",&n); ans=0; while(n--) { scanf("%d",&x); find=1; temp=1; for(int i=0;i<len&& x>=prime[i];i++) if (x%prime[i]==0) { t=prime[i]*prime[i]*prime[i]; while(x%t==0) x/=t; t=prime[i]*prime[i]; if (x%t==0) { x/=t; temp*=t; find*=prime[i]; } else if (x%prime[i]==0) { x/=prime[i]; temp*=prime[i]; find*=t; } } temp*=x;find*=x*x; if (find<=1000000) ans+=vis[find]; vis[temp]++; } printf("%d\n",ans); } return 0; }
