题意：300个质因子小于2000的数中，选取若干个数出来，使他们的乘积为完全平方数。
思路： 如果一个数是完全平方数，那么它的每个质因子的个数都为偶数。
那么我们就可以列出一系列的方程。
a11x1+a12x2+...+a1nxn=0
a21x1+a22x2+...+a2nxn=0
...
an1x1+an2x2+...+annxn=0
aij：第i个质数（2000内有303个质数）在第j个数里是奇数个则为1，否则为0。
xi：第i个数（最多300个数）被选则为1，否则为0。
明显这是个异或方程组。
方案数就是 2^(n-r)-1，r为方程组的秩。-1是减去全不选的情况。
代码为：
#include<stdio.h> #include<string.h> #include<math.h> #include<queue> #include<vector> #include<iostream> #include<complex> #include<string> #include<set> #include<map> #include<algorithm> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define nn 505 #define ll long long #define ULL unsiged long long #define mod 1000000007 #define inf oxfffffffffff #define eps 0.000000001 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 int p[400], vis[2020], cnt; void init() { memset(vis, 0, sizeof(vis)); vis[1] = 1; cnt = 0; for (int i = 2; i <= 2010; i++) { if (!vis[i]) p[cnt++] = i; for (int j = i*i; j <= 2010; j += i) vis[j] = 1; } } int a[nn][nn]; int Rank(int m, int n)//m个方程，n个变量 { int r, u, i = 0, j = 0, k; 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++; } return i;//返回矩阵的秩 } ll quk(ll x, ll k) { ll ans = 1; while (k) { if (k & 1) ans = ans*x%mod; x = x*x%mod; k >>= 1; } return ans; } int main() { init(); int t, kcase = 1; scanf("%d", &t); while (t--) { int n, maxp = 0; scanf("%d", &n); memset(a, 0, sizeof(a)); for (int i = 0; i < n; i++) { ll x; scanf("%lld", &x); for (int j = 0; j < cnt; j++) while (x%p[j] == 0) { maxp = max(maxp, j); x /= p[j]; a[j][i] ^= 1; } } int r = Rank(maxp + 1, n); ll ans = quk(2ll,(ll)n-r); ans = (ans + mod - 1) % mod; printf("Case #%d:\n%lld\n", kcase++, ans); } return 0; } 其实和白书P160的题，一模一样，数据该大贴上去就能A。我也是日了*了。
