Hdu-5833 Zhu and 772002(高斯消元)

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个数字，让你从中选出一些数字出来乘到一起，问能的到完全平方数的方案数。

分析：注意到最大的素因子最多为1997（303个），完全平方数中的所有素因子个数为偶数个，我们可以以此建立一个异或方程组，每个质因子对应一个方程，求出自由元个数的二次幂减一就是答案。

#include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> #include<cmath> #include<queue> #define INF 0x3f3f3f3f #define eps 1e-9 #define MOD 1000000007 using namespace std; int T,n,tot,f[2005],F[310][310]; bool prime[2005]; void Swap(int a[310],int b[310]) //交换 { for(int i = 1;i <= n;i++) a[i] = a[i] + b[i]; for(int i = 1;i <= n;i++) b[i] = a[i] - b[i]; for(int i = 1;i <= n;i++) a[i] = a[i] - b[i]; } long long ksm(long long a,long long b) { long long ans = 1ll; while(b) { if(b & 1) ans = ans * a % MOD; a = a * a % MOD; b >>= 1; } return ans; } int main() { memset(prime,1,sizeof(prime)); prime[2] = true; for(int i = 2;i <= 2000;i++) if(prime[i]) for(int j = 2*i;j <= 2000;j += i) prime[j] = false; for(int i = 2;i <= 2000;i++) if(prime[i]) f[i] = ++tot; scanf("%d",&T); for(int t = 1;t <= T;t++) { int zy = 0; memset(F,0,sizeof(F)); scanf("%d",&n); for(int i = 1;i <= n;i++) { long long x; scanf("%I64d",&x); for(int k = 2;k <= sqrt(x);k++) while(x % k == 0) { F[f[k]][i] = (F[f[k]][i] + 1) % 2; x /= k; } if(x != 1) F[f[x]][i] = 1; } int now = 0; for(int i = 1;i <= n;i++) { int k = ++now; while(F[k][i] == 0 && k < tot) k++; if(F[k][i] == 0) { zy++; now--; continue; } if(k != now) Swap(F[now],F[k]); for(int j = now+1;j <= tot;j++) if(F[j][i] != 0) { for(int k = 1;k <= n;k++) F[j][k] ^= F[now][k]; } } printf("Case #%d:\n%I64d\n",t,(ksm(2,zy)-1LL+MOD)%MOD); } }