本文主要是介绍Zhu and 772002 HDU - 5833 （高斯消元求异或方程组解的个数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5833
题目描述：给定n个数，每个数所含质因子最大不超过2000，选取任意个（至少为1个）数字相乘，要求所得乘积为完全平方数，求共有多少种选取方案。
思路：题目都已经说每个数所含最大质因子不超过2000了，很明显是要分解质因子求解，求的2000以内的素数共303个。要想相乘组成完全平方数，只要所选取的x个数中含有的质因子都是偶数个都行，奇偶可以用10表示，1为奇数个，0为偶数个。首先需要求出每个数所含质因子及其个数，设a[i][j]表示第j个数所含质因子i的个数，0表示偶数个，1表示奇数个。x[i]表示是否选取第i个数。则只需：
a[1][1] *x[1] ^ a[1][2] * x[2] ^ ...... ^ a[1][n] * x[n] = 0
a[2][1] *x[1] ^ a[2][2] * x[2] ^ ...... ^ a[2][n] * x[n] = 0
...........
a[n][1] *x[1] ^ a[n][2] * x[2] ^ ...... ^ a[n][n] * x[n] = 0
这样很明显用高斯消元求矩阵的秩，进而求出自由变量的个数ans，那么方程组X[i]的解的个数为2^ans，注意要减去一个数都不选（即X[i]全为0的情况），故答案为2^ans-1。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<sstream>
#include<deque>
#include<stack>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-6;
const int maxn = 2000 + 10;
const int maxt = 300 + 10;
const int mod = 10;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int Dis[] = {-1, 1, -5, 5};
const int inf = 0x3f3f3f3f;
const int MOD = 1000000007;
ll n, m, k;
int prime[500];//素数表
bool vis[maxn];
int a[maxn][maxn];//a[i][j]表示数字j中含有所含质因子i的个数，奇数个为1，偶数个为0
ll num[maxn];
int cnt;
void getPrime(){//2000以内素数打表memset(prime, 0, sizeof prime);memset(vis, false, sizeof vis);int maxnum = 2000;cnt = 0;for(int i = 2; i <= maxnum; ++i)if(!vis[i]){prime[++cnt] = i;vis[i] = true;for(int j = i * i; j <= maxnum; j += i){vis[j] = true;}}
}
ll Gauss(){//高斯消元int i, j, k, x, y;for(i = 1, j = 1; i <= cnt && j <= n; ++j){k = i;while(k <= cnt && !a[k][j]) ++k;if(a[k][j]){swap(a[i], a[k]);for(x = i + 1; x <= cnt; ++x){if(a[x][j]){for(y = i; y <= n; ++y){a[x][y] ^= a[i][y];}}}++i;}}return (ll)n - (ll)i + 1ll;//自由变量的个数，每个自由变量可以为0也可以为1，故解的个数就是（1<<自由变量个数）
}
ll quick_pow(ll a, ll x){//快速幂ll ans = 1;while(x > 0){if(x & 1) ans = (ans * a) % MOD;x >>= 1;a = (a * a) % MOD;}return ans;
}
int main(){getPrime();int t, kase = 0;scanf("%d", &t);while(t--){scanf("%I64d", &n);ll tmp;memset(a, 0, sizeof a);for(int i = 1; i <= n; ++i){scanf("%lld", &num[i]);tmp = num[i];for(int j = 1; j <= cnt; ++j){//求每个数所含质因子及其个数if(tmp % prime[j] == 0){while(tmp > 0 && tmp % prime[j] == 0){a[j][i] ^= 1;//异或判断有奇数个还是偶数个tmp /= prime[j];}}}}ll x = Gauss();printf("Case #%d:\n", ++kase);printf("%lld\n", quick_pow(2, x) - 1);//减去全为0（也就是一个数都不选）的情况}return 0;
}/*2
3
3 3 4
3
2 2 2*/
这篇关于Zhu and 772002 HDU - 5833 （高斯消元求异或方程组解的个数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
