首页 > 代码库 > SGU 200.Cracking RSA(高斯消元)
SGU 200.Cracking RSA(高斯消元)
时间限制：0.25s
空间限制：4M
题意：
给出了m（<100）个数，这m个数的质因子都是前t(<100)个质数构成的。
问有多少个这m个数的子集，使得他们的乘积是完全平方数。
Solution：
要使乘积为完全平方数，那么对于乘积的每个质因子的个数要为偶数。
可以先打出前100个质数，来看第i个质数Pi，对于第j个数Kj，如果它含有奇数个质数Pi，那么矩阵A[i][j]的值为1,显然增广矩阵的值应该全为0.
这样就构造出了一个n*m的xor方程组.
利用高斯消元求出变元的个数power
那么答案就是(2^power)-1
wa了几次竟然是因为高精度写错了,真是醉了...
code
/* 解异或方程组*/#include <iostream>#include <vector>using namespace std;const int MAXN = 211;int prim[MAXN];vector<int> A[MAXN];int Gauss (int n, int m) { int col = 1, row = 0, tem, k = 0; for (; col <= m && row <= n; ++col) { for (tem = ++row; tem <= n && A[tem][col] == 0; ++tem); if (tem > n) { row--; continue; } if (tem != row) swap (A[tem], A[row]); for (int i = row + 1; i <= n; ++i) { if (A[i][col]) for (int j = col; j <= m; ++j) A[i][j] ^= A[row][j]; } } return m - row;}void init() { bool vis[2200] = {0}; for (int i = 2, tol = 0; i <= 1000; ++i) if (!vis[i]) { prim[++tol] = i; for (int j = i; j <= 1000; j += i) vis[j] = 1; }}int n, m;void output (int x) { if (x <= 0) { cout << 0 << endl; return; } int C[1000] = {0}, len = 1; for (int i = 1; i <= x; ++i) { for (int j = 1; j <= len; ++j) C[j] <<= 1; C[1]++; for (int t = 1; t <= len ; t++) if (C[t] >= 10) { C[t + 1] += C[t] / 10; C[t] %= 10; if (t + 1 > len) len++; } } for (int i = len; i > 0; --i) cout << C[i];}int main() { ios::sync_with_stdio (0); init(); cin >> n >> m; for (int i = 1; i < MAXN; i++) A[i].resize (MAXN); for (int i = 1, x; i <= m; ++i) { cin >> x; for (int j = 1; j <= n; ++j) for (; x % prim[j] == 0; x /= prim[j]) A[j][i] ^= 1; } int power = Gauss (n, m); output (power);}
SGU 200.Cracking RSA(高斯消元)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。