首页 > 代码库 > UVa11542 Square

UVa11542 Square

 

 

 

 1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define LL long long 8 using namespace std; 9 const int mxn=1200;10 int read(){11     int x=0,f=1;char ch=getchar();12     while(ch<0 || ch>9){if(ch==-)f=-1;ch=getchar();}13     while(ch>=0 && ch<=9){x=x*10+ch-0;ch=getchar();}14     return x*f;15 }16 LL read1(){17     LL x=0,f=1;char ch=getchar();18     while(ch<0 || ch>9){if(ch==-)f=-1;ch=getchar();}19     while(ch>=0 && ch<=9){x=x*10+ch-0;ch=getchar();}20     return x*f;21 }22 int pri[mxn],cnt=0;23 bool vis[mxn];24 void Pri(){25     for(int i=2;i<mxn;i++){26         if(!vis[i])pri[++cnt]=i;27         for(int j=1;j<=cnt && pri[j]*i<mxn;j++){28             vis[pri[j]*i]=1;29             if(i%pri[j]==0)break;30         }31     }32     return;33 }34 int T,n,m;35 int a[120][120];36 void solve(){37     int i=0,j=0;38     while(i<=m && j<n){39         int p=i;40         for(int k=i;k<=m;k++)41             if(a[k][j]){p=k;break;}42         if(a[p][j]){43             if(p!=i){44                 for(int k=0;k<=n;k++)45                     swap(a[i][k],a[p][k]);46             }47             for(int l=i+1;l<=m;l++){48                 if(a[l][j]){49                     for(int c=i;c<=n;c++)50                         a[l][c]^=a[i][c];51                 }52             }53             i++;54         }55         j++;56     }57     LL ans=(1LL<<(n-i))-1;58     printf("%lld\n",ans);59     return;60 }61 int main(){62     int i,j;63     Pri();64     T=read();65     LL x;66     while(T--){67         memset(a,0,sizeof a);m=0;68         //69         n=read();70         for(i=0;i<n;i++){71             x=read1();72             for(j=1;i<=cnt && x>1;j++){73                 if(x%pri[j]==0){74                     m=max(m,j);//方程组数量 75                     while(x%pri[j]==0){76                         a[j-1][i]^=1;77                         x/=pri[j];78                     }79                 }80             }81         }82         solve();83     }84     return 0;85 }

 

/*by SilverN*/#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#include<cmath>#define LL long longusing namespace std;const int mxn=1200;int read(){    int x=0,f=1;char ch=getchar();    while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}LL read1(){    LL x=0,f=1;char ch=getchar();    while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}int pri[mxn],cnt=0;bool vis[mxn];void Pri(){for(int i=2;i<mxn;i++){if(!vis[i])pri[++cnt]=i;for(int j=1;j<=cnt && pri[j]*i<mxn;j++){vis[pri[j]*i]=1;if(i%pri[j]==0)break;}}return;}int T,n,m;int a[120][120];void solve(){int i=0,j=0;while(i<=m && j<n){int p=i;for(int k=i;k<=m;k++)if(a[k][j]){p=k;break;}if(a[p][j]){if(p!=i){for(int k=0;k<=n;k++)swap(a[i][k],a[p][k]);}for(int l=i+1;l<=m;l++){if(a[l][j]){for(int c=i;c<=n;c++)a[l][c]^=a[i][c];}}i++;}j++;}LL ans=(1LL<<(n-i))-1;printf("%lld\n",ans);return;}int main(){int i,j;Pri();T=read();LL x;while(T--){memset(a,0,sizeof a);m=0;//n=read();for(i=0;i<n;i++){x=read1();for(j=1;i<=cnt && x>1;j++){if(x%pri[j]==0){m=max(m,j);//方程组数量 while(x%pri[j]==0){a[j-1][i]^=1;x/=pri[j];}}}}solve();}return 0;}

UVa11542 Square