首页 > 代码库 > SGU 200. Cracking RSA 高斯消元

SGU 200. Cracking RSA 高斯消元

比较裸的题了。分解因数后消元便行了,答案就是2的自由元数量次方减一(因为空集不算答案) \(2^k-1\)

 

//{HEADS#define FILE_IN_OUT#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <ctime>#include <algorithm>#include <iostream>#include <fstream>#include <vector>#include <stack>#include <queue>#include <deque>#include <map>#include <set>#include <bitset>#include <complex>#include <string>#define REP(i, j) for (int i = 1; i <= j; ++i)#define REPI(i, j, k) for (int i = j; i <= k; ++i)#define REPD(i, j) for (int i = j; 0 < i; --i)#define STLR(i, con) for (int i = 0, sz = con.size(); i < sz; ++i)#define STLRD(i, con) for (int i = con.size() - 1; 0 <= i; --i)#define CLR(s) memset(s, 0, sizeof s)#define SET(s, v) memset(s, v, sizeof s)#define mp make_pair#define pb push_back#define PL(k, n) for (int i = 1; i <= n; ++i) { cout << k[i] << ‘ ‘; } cout << endl#define PS(k) STLR(i, k) { cout << k[i] << ‘ ‘; } cout << endlusing namespace std;void FILE_INIT(string FILE_NAME) {#ifdef FILE_IN_OUT#ifndef ONLINE_JUDGE     freopen((FILE_NAME + ".in").c_str(), "r", stdin);    freopen((FILE_NAME + ".out").c_str(), "w", stdout);#endif#endif}typedef long long LL;typedef double DB;typedef pair<int, int> i_pair;const int INF = 0x3f3f3f3f;//}const int maxn = 1000 + 5;bool is_prime[maxn];int p[maxn], cnt;void sieve() {    memset(is_prime, true, sizeof is_prime);    for(int i = 2; i < maxn; ++i) {        if(is_prime[i]) {            p[cnt++] = i;            for(int j = i; j < maxn; j += i) {                is_prime[j] = false;            }        }    }}bitset<105> fac[105];int t, m;int d[maxn];int guass() {    int k = 0;    for(int i = 0; k < m && i < t; ++i) {        for(int j = k; j < m; ++j) {            if(fac[j].test(i)) {                if(j != k) {                    swap(fac[j], fac[k]);                }                break;            }        }        if(!fac[k].test(i)) {            continue;        }        for(int j = i + 1; j < m; ++j) {            if(fac[j].test(i)) {                fac[j] ^= fac[i];            }        }        ++k;    }    return m - k;}void divide(int num, int pos) {    for(int i = 0; i < t; ++i) {        while(num % p[i] == 0) {            num /= p[i];            fac[pos].flip(i);        }    }}int ans[100];void answer(int index) {    ans[0] = ans[1] = 1;    for(int i = 1; i <= index; ++i) {        for(int j = 1; j <= ans[0]; ++j) {            ans[j] *= 2;        }        for(int j = 1; j <= ans[0]; ++j) {            if(ans[j] > 9) {                ans[j + 1] += ans[j] / 10;                ans[j] %= 10;            }        }        while(ans[ans[0] + 1] > 0) {            ++ans[0];        }    }    ans[1] -= 1;    for(int i = 1; i <= ans[0]; ++i) {        if(ans[i] < 0) {            ans[i] += 10;            ans[i + 1] -= 1;        }    }    for(int i = ans[0]; 0 < i; --i) {        printf("%d", ans[i]);    }    if(ans[0] == 0) {        printf("0");    }    puts("");}int main() {    FILE_INIT("200");    sieve();    scanf("%d%d", &t, &m);    for(int i = 0; i < m; ++i) {        scanf("%d", &d[i]);        divide(d[i], i);    }    int num = guass();    //printf("%d\n", num);    answer(num);    return 0;}