给一个集合S，问S有多少个子集满足子集中的数乘积是完全平方组。
一个数是完全平方数当且仅当它所有的质因数都有偶数个，所以只要看这个集合中所有数的质因数是否是偶数个即可。和开灯方案数问题类似，矩阵中X[i][j]=1表示第j个数的第i个质因数(2,3,5,7...)有奇数个，等于0表示有偶数个。然后列出XOR方程组然后算有几个自由基即可。
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 typedef long long LL; 6 int cas, n; 7 LL nx; 8 int isp[505], prs, pri[505]; 9 int x[505][505]; 10 void init(){ 11 for (int i = 2; i < 501; i++) if(!isp[i]) 12 for (int j = i*2; j < 501; j += i) isp[j] = 1; 13 for (int i = 2; i < 501; i++) if(!isp[i]) pri[prs++] = i; 14 } 15 int gauss(int totr, int totc) { 16 int r = 0, c = 0; 17 while (r < totr && c < totc) { 18 int maxr = r; 19 for (int i = r+1; i < totr; i++) 20 if (x[i][c]) maxr = i; 21 if (x[maxr][c] != 0) { 22 if (maxr != r) 23 for (int i = 0; i <= totc; i++) swap(x[maxr][i], x[r][i]); 24 for (int i = r+1; i < totr; i++) if(x[i][c]){ 25 for (int j = c; j <= totc; j++) x[i][j] ^= x[r][j]; 26 } 27 r++; 28 } 29 c++; 30 } 31 return totc - r; 32 } 33 int main(){ 34 //freopen("test.in","r",stdin); 35 init(); 36 scanf("%d", &cas); 37 while (cas--) { 38 scanf("%d", &n); 39 memset(x, 0, sizeof x); 40 for (int i = 0; i < n; i++) { 41 scanf("%lld", &nx); 42 for (int j = 0; j < prs; j++) { 43 while (nx % pri[j] == 0) 44 nx /= pri[j], x[j][i] ^= 1; 45 } 46 } 47 int l = gauss(prs, n); 48 printf("%lld\n", (1LL<<l)-1); 49 50 } 51 return 0; 52 }