比赛的时候把三题更水的题做完之后，想此题想了三个多小时。尽管啥都想到了，奈何不懂高斯求元一说，后看此题最后最后通过人数达到400+，不是原题的话应该也没这么过分。
【邝斌模版代码】
#include <set> #include <map> #include <stack> #include <queue> #include <deque> #include <cmath> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define L(i) i<<1 #define R(i) i<<1|1 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 1e-9 #define maxn 100010 //#define MOD 1000000007 const long long MOD = 1000000007; const int MAXN = 1805; //有equ个方程，var个变元。增广矩阵行数为equ,列数为var+1,分别为0到var int a[MAXN][MAXN]; //增广矩阵 int x[MAXN]; //解集 int free_x[MAXN];//用来存储自由变元（多解枚举自由变元可以使用） int free_num;//自由变元的个数 //返回值为-1表示无解，为0是唯一解，否则返回自由变元个数 int Gauss(int equ,int var) { int max_r,col,k; free_num = 0; for(k = 0, col = 0 ; k < equ && col < var ; k++, col++) { max_r = k; for(int i = k+1; i < equ; i++) { if(abs(a[i][col]) > abs(a[max_r][col])) max_r = i; } if(a[max_r][col] == 0) { k--; free_x[free_num++] = col;//这个是自由变元 continue; } if(max_r != k) { for(int j = col; j < var+1; j++) swap(a[k][j],a[max_r][j]); } for(int i = k+1; i < equ; i++) { if(a[i][col] != 0) { for(int j = col; j < var+1; j++) a[i][j] ^= a[k][j]; } } } for(int i = k; i < equ; i++) if(a[i][col] != 0) return -1; //无解 if(k < var) return var-k;//自由变元个数 //唯一解，回代 for(int i = var-1; i >= 0; i--) { x[i] = a[i][var]; for(int j = i+1; j < var; j++) x[i] ^= (a[i][j] && x[j]); } return 0; } int prime[330],k; int vis[2005]; void gen_primes(int m) { memset(vis, 0, sizeof(vis)); k = 0; for (int i = 2; i < m; i++) { if (!vis[i]) { prime[k++] = i; for (int j = i * i; j < m; j += i) vis[j] = 1; } } } int main() { //get_prime(); gen_primes(2000); int t,C = 1; scanf("%d", &t); while(t--) { int n; scanf("%d", &n); memset(a,0,sizeof(a)); for(int i = 0; i < n; i++) { long long xx; scanf("%lld",&xx); for(int j = 0; j < k; j++) if(xx % prime[j] == 0) { while(xx % prime[j] == 0) { xx /= prime[j]; a[j][i] ^= 1; } } } int m = Gauss(k,n); long long ans = 1; for(int i = 0; i < m; i++) ans = ans * 2 % MOD; printf("Case #%d:\n",C++); printf("%lld\n",(ans-1+MOD)%MOD); } return 0; }
