ZOJ 2320 Cracking' RSA

忘是亡心i 2022-03-29 06:39 139阅读 0赞

其次布尔线性方程组，高斯消元。这道题目的关键部分是看的神牛[watashi][]的思路。另附上watashi的思路

![20131031180428593][]

我把他的java模板翻译成了C++的了。。。存起来以后当模板用。。。a\[i\]\[j\]表示第i个数含有质数p\[j\]的个数，奇数个的话就是true，偶数个就是false。这样的话对于布尔方程组有，能被完全消掉的数就可以和用来消去这个数的数组成一个完全平方数。这样的话就是找多少个数能够被完全消去。这样的话答案就是2^（n-r）-1了。

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #define LL long long
    #define CLR(a, b) memset(a, b, sizeof(a))
    
    using namespace std;
    const int N = 120;
    const int M = 600;
    bool a[N][N];
    bool isp[M];
    int p[N], cnt;
    
    void get_P()
    {
        CLR(isp, true);cnt = 0;
        isp[0] = isp[1] = false;
        for(int i = 2; i < M; i ++)
        {
            if(isp[i])
            {
                p[cnt ++] = i;
                for(int j = i * i; j < M; j += i) isp[j] = false;
            }
        }
    }
    
    int gauss(int N, int M)
    {  
        int r, c, pvt;  
        bool flag;
        for (r = 0, c = 0; r < N && c < M; ++ r, ++ c) {
            flag = false;
            for (int i = r; i < N; ++ i)  
                if (a[i][c]) {
                    flag = a[pvt=i][c];
                    break;
                }
            if (!flag) {  
                r--; continue;  
            }  
            if (pvt != r)  
                for (int j = r; j <= M; ++j) swap(a[r][j], a[pvt][j]);  
            for (int i = r+1; i < N; ++i)  
                if(a[i][c])
                {
                    a[i][c] = false; 
                    for (int j = c+1; j <= M; ++j) {  
                        if(a[r][j]) a[i][j] = !a[i][j];
                }
            }
        } 
        return r;
    }
    
    int ans[N], MOD = 10000;
    
    void pt(int n)
    {
        int bit = 0, cr = 0;
        CLR(ans, 0);ans[0] = 1;
        for(int i = 0; i < n; i ++)
        {
            cr = 0;
            for(int j = 0; j <= bit; j ++)
            {
                ans[j] = ans[j] * 2 + cr;
                cr = ans[j] / MOD;
                ans[j] %= MOD;
            }
            if(cr) ans[++ bit] = cr;
        }
        int s = 0;
        while(!ans[s]) s ++;ans[s] --;
        for(int i = s - 1; i >= 0; i --)
        {
            ans[s] = MOD - 1;
        }
        //cout << "bit " << bit << endl;
        printf("%d", ans[bit]);
        for(int i = bit - 1; i >= 0; i --)
        {
            int tmp = ans[i], cnt = 0;
            while(tmp){ tmp /= 10; cnt ++;}
            for(int j = 0; j < 4 - cnt; j ++) putchar('0');
            printf("%d", ans[i]);
        }
        puts("");
    }
    
    int main()
    {
        int t, n, m;get_P();
        scanf("%d", &t);
        while(t --)
        {
            scanf("%d%d", &m, &n);
            for(int i = 0; i < n; i ++)
            {
                int tmp;
                scanf("%d", &tmp);
                for(int j = 0; j < m; j ++)
                {
                    a[i][j] = false;
                    while(tmp % p[j] == 0)
                    {
                        tmp /= p[j];
                        a[i][j] = !a[i][j];
                    }
                }
            }
            n -= gauss(n, m);
            pt(n);
            if(t) puts("");
        }
    }

[watashi]: http://blog.watashi.ws/623/andrew-stankevich-1-solutio/
[20131031180428593]: /images/20220329/07a79d9abbb94d5baff0fcfba8c52771.png