SGU 200 Cracking RSA (고 스 소원 + 대수 고정 밀도)

제목: SGU 200
이 문 제 는 뜻밖에도 높 은 정밀도 로 시험 을 보 았 다.어이 가 없다.
이 인자 의 짝수 개 를 0 으로 하고 홀수 개 를 1 로 하면 이 또는 연산 을 만족 시 킬 수 있 습 니 다. 즉, 기 + 기 = 우, 우 + 우 = 우, 기 + 우 = 기.그리고 방정식 을 만 들 고 고 스 소원 구 변 원 개수 freenum, 그럼 부분 집합 개 수 는 2 ^ free 입 니 다.num-1。1 을 빼 는 것 은 0 을 빼 는 경우 다.대수 연산 에 주의해 야 한다.
코드 는 다음 과 같 습 니 다:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=1e9;
const double eqs=1e-9;
int mat[120][120], a[120], equ, var, prime[120];
int c[100];
int gauss()
{
        int i, j, k, h, max_r, tmp;
        for(i=0,j=0;i<equ&&j<var;i++,j++){
                max_r=i;
                for(k=i+1;k<equ;k++){
                        if(mat[k][j]>mat[max_r][j]) max_r=k;
                }
                if(max_r!=i){
                        for(k=j;k<=var;k++){
                                swap(mat[i][k],mat[max_r][k]);
                        }
                }
                if(mat[i][j]==0){
                        i--;
                        continue ;
                }
                for(k=i+1;k<equ;k++){
                        if(mat[k][j]==0) continue ;
                        for(h=j;h<=var;h++){
                                mat[k][h]^=mat[i][h];
                        }
                }
        }
        tmp=i;
        //printf("%d
",tmp);
        for(;i<equ;i++){
                if(mat[i][var]){
                        return 0;
                }
        }
        return var-tmp;
}
void output(int k)
{
        int i, j, x, y, tmp;
        memset(c,0,sizeof(c));
        c[0]=1;
        x=0;
        for(i=0;i<k;i++){
                for(j=0;j<=80;j++){
                        y=(c[j]*2+x)%10;
                        x=(c[j]*2+x)/10;
                        c[j]=y;
                }
        }
        for(i=80;i>=0;i--){
                if(c[i]){
                        tmp=i;
                        break;
                }
        }
        c[0]--;
        for(i=tmp;i>=0;i--){
                printf("%d",c[i]);
        }
        puts("");
}
void init()
{
        int i, j, cnt=0, flag;
        for(i=2;;i++){
                flag=0;
                for(j=2;j*j<=i;j++){
                        if(i%j==0){
                                flag=1;
                                break;
                        }
                }
                if(!flag){
                        prime[cnt++]=i;
                }
                if(cnt==100) return ;
        }
}
int main()
{
        int t, n, i, j, x, cnt, ans;
        init();
        scanf("%d%d",&t,&n);
        for(i=0; i<n; i++) {
                scanf("%d",&a[i]);
        }
        for(i=0; i<n; i++) {
                x=a[i];
                for(j=0;j<t;j++){
                        cnt=0;
                        while(x%prime[j]==0){
                                cnt++;
                                x/=prime[j];
                        }
                        mat[j][i]=(cnt&1);
                }
        }
        for(i=0;i<t;i++){
                mat[i][n]=0;
        }
        equ=t;
        var=n;
        ans=gauss();
        if(ans)
        output(ans);
        else puts("0");
        return 0;
}