@Chilling
2017-07-08T20:34:53.000000Z
字数 2179
阅读 825
高斯消元
Problem Description
Zhu and 772002 are both good at math. One day, Zhu wants to test the ability of 772002, so he asks 772002 to solve a math problem.
But 772002 has a appointment with his girl friend. So 772002 gives this problem to you.
There are n numbers a1,a2,...,an. The value of the prime factors of each number does not exceed 2000, you can choose at least one number and multiply them, then you can get a number b.
How many different ways of choices can make b is a perfect square number. The answer maybe too large, so you should output the answer modulo by 1000000007.
Input
First line is a positive integer T , represents there are T test cases.
For each test case:
First line includes a number ,next line there are n numbers a1,a2,...,an,.
Output
For the i-th test case , first output Case #i: in a single line.
Then output the answer of i-th test case modulo by 1000000007.
Sample Input
2
3
3 3 4
3
2 2 2
Sample Output
Case #1:
3
Case #2:
3
题意: t组样例,每组样例输入一个n,表示有n个数ai,要从这n个数中随便选几个出来,让他们的乘积成为一个完全平方数,问有多少种方案。方案数模1e9+7。
分析:首先,对于一个完全平方数来说,它的每个相同素因子,一定有偶数个,比如36,素因子2,2,3,3,2和3都是两个。那么我们将每一个输入的x进行素因子分解。一个列数为n的矩阵,行表示素数,从上到下分别为素数2,3,5,7……出现的次数。如果某个素因子出现奇数次,那么记为1,否则为0。如第一个数素因子分解之后,素因子3出现奇数次,其他都为偶数次,那么mp[1][0]=1,其他mp[i][0]为0。
由于完全平方数相同素因子为偶数个,也就是说,将这个矩阵进行高斯消元之后,增广矩阵最后一列为全0。我们求出自由元的个数fre,那么是否就为最终的答案?不……还要刨去所有数都不选的情况,因此得到……
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=350;
const int mod=1e9+7;
int prime[350],cnt;
int mp[350][350];
void getPrime()
{
prime[cnt++]=2;
for(int i=3;i<=2000;i+=2)
{
int flag=1;
for(int j=2;j*j<=i;j++)
{
if(i%j==0)
{
flag=0;
break;
}
}
if(flag) prime[cnt++]=i;
}
}
int resolution(int col,LL x)
{
int m=0;
for(int i=0;i<cnt;i++)
{
while(x%prime[i]==0)
{
mp[i][col]^=1;
x/=prime[i];
m=max(m,i+1);
}
}
return m;
}
int gauss(int A[][maxn],int n,int m)
{
int res=0,r=0;
for(int i=0;i<m&&r<m;i++)
{
for(int j=r;j<n;j++)
{
if(A[j][i]==1)
{
for(int k=i;k<=m;k++)
swap(A[j][k],A[r][k]);
break;
}
}
if(A[r][i]==0)
{
res++;
continue;
}
for(int j=0;j<n;j++)
{
if(A[j][i]==1&&j!=r)
{
for(int k=i;k<=m;k++)
A[j][k]^=A[r][k];
}
}
r++;
}
return res;
}
int main()
{
int t,o=0;
getPrime();
scanf("%d",&t);
while(t--)
{
memset(mp,0,sizeof(mp));
LL x;
int n,y=0,fre=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%lld",&x);
y=max(y,resolution(i,x));
}
fre+=gauss(mp,y,n);
LL ans=1;
for(int i=1;i<=fre;i++)
ans=ans*2%mod;
ans--;
printf("Case #%d:\n%lld\n",++o,ans);
}
return 0;
}