。。这道题目模线性方程组的模型很好想。。关键是高斯消元。。我搞的累死就是因为很多地方写错了。。。
幸好还是过了。。
Code。。注意。。消元找主元的时候一定要考虑所有没被消过的元素。。。
#include<iostream>
using namespace std;
const int maxn=100+10;
int A[maxn][maxn]={0};
int P[maxn];
int n,m;
void add(string& a,string b,string c)
{
int d=0,t=max(b.length(),c.length());a="";
for(int i=0;i<t;i++)
{
d+=b[i]+c[i]-2*’0′;
a+=char(d%10+’0′);
d/=10;
}   
if(d)
a+=’1′;
}
void sub(string&a)
{       
a[0]-=1;       
}
void print(const string&a)
{
for(int i=a.length()-1;i>=0;i–)
cout<<a[i];
}
bool isprime(int p)
{
if(p==2) return true;
if(p%2==0) return false;
for(int i=3;i*i<=p;i+=2)
if(p%i==0) return false;
return true;
}
void swap(int&x,int&y)
{int t=x;x=y;y=t;}
int main()
{
cin>>n>>m;
int now=2;
for(int i=0;i<n;i++)
{
while(!isprime(now))
now++;
P[i]=now++;
}
for(int i=0;i<m;i++)
{
int p,t=0;
cin>>p;
for(int j=0;j<n;j++)
{
t=0;
while(p%P[j]==0)
p/=P[j],t++;
A[j][i]=t%2;
}
}
int i;
for(i=0;i<min(n,m);i++)
{
int p,q;
for(p=i;p<n;p++)
for(q=i;q<m;q++)
if(A[p][q]) goto out;
out:
if(p==n)break;
for(int o=0;o<n;o++)
swap(A[o][i],A[o][q]);
for(int o=0;o<=m;o++)
swap(A[i][o],A[p][o]);
for(int o=0;o<n;o++)if(o!=i&&A[o][i])
for(int j=0;j<=m;j++)
A[o][j]^=A[i][j];
}
i=m-i;
string ans="1";
while(i–)
{
add(ans,ans,ans);
}
sub(ans);
print(ans);
}