HDU 5833 Zhu and 772002 高斯消元

原题见HDU 5833

在 n 个数中选择几个数ai相乘得到平方数，问有多少种取法。最大的素因子不超过2000，最后答案mod 1000000007。 (1≤n≤300,1≤ai≤1018)

---

分析

所有数的因子不超过2000，则可以打表得到所有可能的因子共pn个。并得到每个因子属于第几个。 对每个数整数分解，可以得到由因子的指数形成的pn维向量。如 4->(2,0,0,…) 90->(1,2,1,…) 省略部分为0.

题意等价于选取一些向量，使得向量和的每个分量都是偶数。 其实分量只要看奇偶，即模2为1或0.因此每个向量的分量只要标明是1或0，而不必看是否是大于1的数。 4->(0,0,0,…) 90->(1,0,1,0,0,…)

若选取第i个向量，则令 xi=1 ，否则为0.

现在把每个向量竖着写，形成一个pn*n的矩阵A，令 X=(x1,x2,...xn)−1 ，最后的结果为 β=(0,0,...,0)−1 。题意即等价于求方程 AX=β 的解 X 的个数。 这个过程由高斯消元搞定。

由线性代数的性质可知，只要求A的秩r，即可得自由元有n-r个，且每个元的解集为{0,1}，故共有 2n−r 个解。其中必有解 (0,0,0,...,0) 但因为这个解表示并不取任何数，故要舍去。最后要求的是 (2n−r−1)%1000000007

---

代码

#include <bits/stdc++.h> using namespace std; #define N 2000 #define LL long long int num[N], prim[N], pn = 0, a[N][N], mod=1000000007; void table() { memset(num, -1, sizeof(num)); for(int i = 2;i < N;i++) { if(num[i]) prim[pn++] = i; for(int j = 0;j < pn && 1LL*prim[j]*i < N;j++) { int t = prim[j] * i; num[t] = 0; if(i % prim[j] == 0) break; } } } int n, m; int gauss()//根据伪代码这个很好理解 { int i, j, k, id; for(i = 0, j = 0; i < m,j < n;) { id = i; for(k = i+1; k < m; k++) if(abs(a[k][j]) > abs(a[id][j])) id = k; if(id != i) { for(k = j; k < n; k++) swap(a[i][k],a[id][k]); }//使a[id][k](i<=k<=n)是最 大的,并把这行移到第i行 if(a[i][j] == 0) { j++; continue; }//最大的a[id][k]=0 for(k = i+1; k < m; k++)//线性变换化0 { if(a[k][j] == 0) continue; for(int l = j; l < n; l++) a[k][l] = a[k][l] ^ a[i][l]; } i++,j++; } for(int k = i; k < m; k++) if(a[k][n] != 0) { return -1;//根据前面说的，无解 } return n-i; } LL powo(LL a, int k) { if(k == 0) return 1; if(k == 1) return a; LL tmp = powo(a, k/2); tmp = tmp * tmp % mod; if(k & 1) tmp *= a; return tmp % mod; } void solve() { int x = gauss(); LL ans = powo(2, x) - 1; ans = (ans % mod + mod) % mod; printf("%lld\n", ans); } int main() { int T, o = 0; table(); scanf("%d", &T); while(T--) { scanf("%d", &n); m = 0; memset(a, 0, sizeof(a)); for(int i = 0;i < n;i++) { LL t; scanf("%lld", &t); for(int j = 0;j < pn && prim[j] <= t;j++) { while(t % prim[j] == 0) { t /= prim[j]; a[j][i]++; } a[j][i] &= 1; if(a[j][i]) m = max(m, j+1); } } printf("Case #%d:\n", ++o); solve(); } return 0; }