链接：http://acm.hdu.edu.cn/showproblem.php?pid=5833
题意：给你n个数，每个数的素数因子最大不超过2000，从n个数取出1~n个，问有多少种方案使得腾门乘积为完全平方数。
分析：我们知道完全平方数分解后的所有素数的都是偶数次方的，所以我们可以将所有数都素因素分解，可以得到选出来的数都是2^(x1+x2...)*3^(x1+x2....) ...这种形式。
那么我们可以得到素数个方程，n个未知数 ：
ax1+bx2+cx3.....≡0（mod2）; 因为是mod2，所以我们可以装换成求解异或方程的自由变元个数，最后答案就是2^(var-k)-1.减去空集。
........
2016ccpc网络预选赛三道原题之一，见大白160页 uva11542。
代码：
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<queue> #include<cmath> #include<stack> #include<set> #include<map> #define INF 0x3f3f3f3f #define Mn 100010 #define Mm 2000005 #define mod 1000000007 #define CLR(a,b) memset((a),(b),sizeof((a))) #define CLRS(a,b,Size) memset((a),(b),sizeof((a[0]))*(Size+1)) #define CPY(a,b) memcpy ((a), (b), sizeof((a))) #pragma comment(linker, "/STACK:102400000,102400000") #define ul u<<1 #define ur (u<<1)|1 using namespace std; typedef long long ll; int a[2005][2005]; int x[2005]; int prime[1005],no[2005],tot; void getPrime() { for(int i=2;i<=2000;i++) { if(!no[i]) prime[tot++]=i; for(int j=0;prime[j]*i<=2000;j++) { no[prime[j]*i]=1; if(i%prime[j]==0) break; } } } int gauss(int equ,int var) { int k,col,max_r; for(col=0,k=0;k<equ&&col<var;k++,col++) { max_r=k; for(int i=k+1;i<equ;i++) if(a[i][col]) { max_r=i; break; } if(max_r!=k) for(int j=col;j<=var;j++) swap(a[k][j],a[max_r][j]); if(a[k][col]==0) { k--; continue; } for(int i=k+1;i<equ;i++) if(a[i][col]){ for(int j=col;j<=var;j++) a[i][j]^=a[k][j]; } } return var-k; } int erp[2005]; int main() { int T; getPrime(); erp[0]=1; for(int i=1;i<=2000;i++) erp[i]=(erp[i-1]*2)%mod; scanf("%d",&T); for(int cas=1;cas<=T;cas++) { int n,maxx=0; CLR(a,0); scanf("%d",&n); for(int i=0;i<n;i++) { ll b; scanf("%I64d",&b); for(int j=0;j<tot;j++) { while(b%prime[j]==0) { maxx=max(maxx,j+1); b/=prime[j]; a[j][i]^=1; } } } printf("Case #%d:\n%d\n",cas,erp[gauss(maxx,n)]-1); } return 0; }