题目大意：给出n个数a[i]，选择其中一些数相乘，求能得到一个完全平方数的方案数（每个数限用一次），保证每个数都不包含超过500的质因子 n<=100,ai<=10^15 数据保证结果在64位整型以内
题解： 因为每个数都不包含超过500的质因子，所以很容易想到将这些数唯一分解，表示成每个质因子的个数，因为完全平方数的特征是：每个质因数的个数一定是偶数个，所以可以将每个数表示成一个二进制数，代表这个数的第i个质因子为奇数/偶数个，以此再列出方程式，求解即可。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<bitset> #define SF scanf #define PF printf #define MAXN 1010 using namespace std; bitset<MAXN> a[MAXN]; int n,f[MAXN],d[MAXN],tot,d1[MAXN],sum; long long m,Rank; long long num[MAXN]; void prepare(){ bool flag; for(int i=2;i<=500;i++){ flag=1; for(int j=2;j<=i/2;j++) if(i%j==0){ flag=0; break; } if(flag) d[tot++]=i; } } void init(){ sum=0; memset(a,0,sizeof a); SF("%d",&n); for(int i=0;i<n;i++) SF("%lld",&num[i]); for(int i=0;i<tot;i++) for(int j=0;j<n;j++) if(num[j]%d[i]==0){ d1[sum++]=d[i]; break; } for(int i=0;i<n;i++) for(int j=0;j<sum;j++) while(num[i]!=0&&num[i]