高斯消元。求有多少不同组解。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } template <class T> inline void read(T &x) { char c = getchar(); x = 0;while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } } const int MAXN=310; int equ, var;///equ个方程 var个变量 int a[MAXN][MAXN];///增广矩阵 int x[MAXN];///解的数目 bool free_x[MAXN];///判断是不是自由变元 int free_num;///自由变元的个数 inline int GCD(int m, int n) { if(n == 0) return m; return GCD(n, m%n); } inline int LCM(int a, int b) { return a/GCD(a,b)*b; } int Gauss() { int Max_r;///当前列绝对值最大的存在的行 ///col：处理当前的列 int row = 0; int free_x_num; int free_index = -1; for(int col=0; row<equ&&col<var; row++,col++) { Max_r = row; for(int i=row+1; i<equ; i++) if(abs(a[i][col]) > abs(a[Max_r][col])) Max_r = i; if(Max_r != row) for(int i=0; i<var+1; i++) swap(a[row][i], a[Max_r][i]); if(a[row][col] == 0) { row--; continue; } for(int i=row+1; i<equ; i++) { if(a[i][col]) { int lcm = LCM(abs(a[i][col]), abs(a[row][col])); int tp1=lcm/abs(a[i][col]), tp2=lcm/abs(a[row][col]); if(a[row][col]*a[i][col] < 0) tp2 = -tp2; for(int j=col; j<var+1; j++) { a[i][j] = tp1*a[i][j]-tp2*a[row][j]; a[i][j] = (a[i][j]%2+2)%2; } } } } if(row < var) { for(int i=row-1; i>=0; i--) { free_x_num = 0; for(int j=0; j<var; j++) if(a[i][j] && free_x[j]) { free_x_num++; free_index = j; } if(free_x_num>1 || free_index==-1) continue; int tmp = a[i][var]; for(int j=0; j<var; j++) if(a[i][j] && j!=free_index) { tmp -= a[i][j]*x[j]; tmp = (tmp%2+2)%2; } x[free_index] = (tmp*a[i][free_index]);/// 求出该变元. x[free_index] %= 2; free_x[free_index] = 0; /// 该变元是确定的. } return var - row;///自由变元的个数 } for(int i=var-1; i>=0; i--) { int tmp = a[i][var]; for(int j=i+1; j<var; j++) if (a[i][j]) { tmp -= a[i][j]*x[j]; tmp = (tmp%2+2)%2; } x[i] = tmp*a[i][i]; x[i] %= 2; } return 0;///唯一解 } const int maxn=2005; bool f[maxn]; int p[maxn], t; void prime() { for(int i=2;i<=2000;i++) f[i]=1; for(int i=2;i<=2000;i++) { if(!f[i]) continue; p[t++]=i; int tmp=2*i; while(tmp<=2000) f[tmp]=0,tmp=tmp+i; } } int T,n; int main() { prime(); int cas=1; scanf("%d",&T); while(T--) { scanf("%d",&n); memset(a,0,sizeof a); memset(x,0,sizeof x); memset(free_x,0,sizeof free_x); free_num=0; for(int i=0;i<n;i++) { LL num; scanf("%lld",&num); for(int j=0;j<t;j++) { while(num%p[j]==0) num=num/p[j],a[j][i]++; a[j][i]=a[j][i]%2; } } equ=t; var=n; int S = Gauss(); long long ans=1, MOD=1e9+7; for(int i=1;i<=S;i++) ans=ans*2%MOD; printf("Case #%d: ",cas++); printf("%lld ",(ans-1+MOD)%MOD); } return 0; }