Zhu and 772002

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Problem Description Zhu and 772002 are both good at math. One day, Zhu wants to test the ability of 772002, so he asks 772002 to solve a math problem. But 772002 has a appointment with his girl friend. So 772002 gives this problem to you. There are n numbers a1,a2,...,an . The value of the prime factors of each number does not exceed 2000 , you can choose at least one number and multiply them, then you can get a number b . How many different ways of choices can make b is a perfect square number. The answer maybe too large, so you should output the answer modulo by 1000000007 .   Input First line is a positive integer T , represents there are T test cases. For each test case: First line includes a number n(1≤n≤300) ，next line there are n numbers a1,a2,...,an,(1≤ai≤1018) .   Output For the i-th test case , first output Case #i: in a single line. Then output the answer of i-th test case modulo by 1000000007 .   Sample Input 2 3 3 3 4 3 2 2 2   Sample Output Case #1: 3 Case #2: 3 题意：给你n个数，现在可以取任意个数，他们的乘积是个完全平方数，一共有多少种取法。 题解：高斯消元法，先分解质因子，因为可以开方，所以对于一个答案，它的所有质因子都是偶数个，所以可以异或来考虑。 假设有x个自由变量，那么答案就是(2^x-1)%1000000007，因为题中说最少取一个数，所以要-1。 可以这样考虑，横列的自由变量的个数，就相当于纵列的n-r，r为旋转后矩阵的秩。 #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; typedef long long ll; ll m,prime[305],vis[2005]; ll a[305][305]; void init(){ ll i,j; for(i=2;i<=2000;i++){//筛选素数 if(!vis[i])prime[++m]=i; for(j=2;j*i<=2000;j++){ vis[i*j]=1; if(!(i%j))break; } } } ll ranks(ll a[][305],ll m,ll n){ ll i=1,j=1,k,r,u; while(i<=m&&j<=n){//处理第i个方程，第j个变量 r=i; for(k=i;k<=m;k++){//寻找开头为1的第一个方程 if(a[k][j]){ r=k; break; } } if(a[r][j]){ if(r!=i){//如果不是在开头，那就交换 for(k=1;k<=n;k++)swap(a[r][k],a[i][k]); } for(u=i+1;u<=m;u++){//把下边的都消掉 if(a[u][j]){ for(k=i;k<=n;k++){ a[u][k]^=a[i][k]; } } } i++;//矩阵的秩+1 } j++; } return i-1;//因为开始的时候i为1，所以这里要-1 } ll solve(ll n,ll x){//快速幂 ll ans=1; while(x){ if(x&1){ ans=ans*n%1000000007; } n=n*n%1000000007; x>>=1; } return ans; } int main(){ ll t,cas=1; init(); scanf("%lld",&t); while(t--){ memset(a,0,sizeof(a)); ll maxp=0,x,n,i,j; scanf("%lld",&n); for(i=1;i<=n;i++){ scanf("%lld",&x); for(j=1;j<=m;j++){ while(x%prime[j]==0){//分解质因子 maxp=max(maxp,j); x/=prime[j]; a[j][i]^=1;//矩阵翻转过来处理 } } } ll r=ranks(a,maxp,n); printf("Case #%d:\n",cas++); cout<<((solve(2,n-r)-1+1000000007)%1000000007)<<endl; } return 0; }