Zhu and 772002

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 510    Accepted Submission(s): 170 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   完全平方数就是每一个素因子的个数都是偶数

那么我们把每个数进行质因数分解，奇数个记为1，偶数个记为0，最后就是求一个异或方程组的解的个数。

#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> using namespace std; const int MAXN =310; const int INF =1000000007 ; const int MOD =1000000007; const double EPS=1e-8; const double pi = acos(-1); int prime[MAXN]; int A[MAXN][MAXN]; int num=0; bool is_prime[2010]={true}; long long powmod(long long a,long long n)//快速幂取膜 { long long res=1; while(n){ if(n&1) res=res*a%MOD; a=a*a%MOD; n>>=1; } return res; } long long solve(int m,int n)//根据系数矩阵求自由变元数量 { int i=0,j=0,k,r,u; while(i<m&&j<n){ r=i; for(k=i; k<m; k++) if(A[k][j]){r=k; break;} if(A[r][j]){ if(r!=i) for(k=0; 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++; } j++; } long long ans=powmod(2,n-i)-1; return ans; } long long a[MAXN]; void getprime()//求出2000以内素数表 { memset(is_prime,true,sizeof(is_prime)); is_prime[2]=true; for(int i=2;i<=2000;i++){ if(is_prime[i]){ prime[num++]=i; for(int j=2*i;j<=2000;j+=i){ is_prime[j]=false; } } } } void get_key(int i)//素数分解 { long long temp=a[i]; for(int k=0;k<num;k++){ while(temp%prime[k]==0){ A[k][i]^=1; temp/=prime[k]; } } } int main() { int t; scanf("%d",&t); getprime(); for(int cas =1;cas<=t;cas++){ int n; scanf("%d",&n); memset(A,0,sizeof(A)); printf("Case #%d:\n",cas); for(int i=0;i<n;i++){ scanf("%I64d",a+i); get_key(i); } printf("%I64d\n",solve(num,n)); } }