首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。