【HDU 5833】Zhu and 772002(异或方程组高斯消元)

300个最大质因数小于2000的数,选若干个它们的乘积为完全平方数有多少种方案。

合法方案的每个数的质因数的个数的奇偶值异或起来为0。

比如12=2^2*3,对应的奇偶值为01(2的个数是偶数为0,3的个数是奇数为1),3的对应奇偶值为01,于是12*3是完全平方数。

然后异或方程组就是:

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-rank)种,减去全为0的解)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define ll long long
#define mod 1000000007
using namespace std;
const int N=;
const int M=;
int prime[N+],cnt;
int n,t,mat[M][M],two[M]={};
ll a[M];
void getPrime(){
for(int i=;i<=N;i++){
if(!prime[i])prime[++cnt]=i;
for(int j=;j<=cnt&&prime[j]<=N/i;j++){
prime[prime[j]*i]=;
if(i%prime[j]==)break;
}
}
}
int Rank(int c[][M]){//异或版的高斯消元求秩
int i=,j=,k,r,u;
while(i<=cnt&&j<=n){
r=i;
while(c[r][j]==&&r<=cnt)r++;
if(c[r][j]){
swap(c[i],c[r]);
for(u=i+;u<=cnt;u++)if(c[u][j])
for(k=i;k<=n;k++)c[u][k]^=c[i][k];
i++;
}
j++;
}
return i;
}
int solve(){
memset(mat,,sizeof mat);
for(int i=;i<=n;i++)
for(int j=;j<=cnt;j++){
ll tmp=a[i];
while(tmp%prime[j]==){
tmp/=prime[j];
mat[j][i]^=;
}
}
int b=n-Rank(mat);//b个*元
return two[b]-;//减去全为0的解
}
int main() {
getPrime();
for(int i=;i<M;i++)two[i]=two[i-]*%mod;
scanf("%d",&t);
for(int cas=;cas<=t;cas++){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lld",&a[i]);
printf("Case #%d:\n%d\n",cas,solve());
}
return ;
}

  原来是白书上的题(160页)I good vagetable a!

上一篇:WebApi调试中遇到的一些问题


下一篇:Python进阶6-异常处理