pollard_rho
Tag: Pollard_Rho
【BZOJ 4522】[Cqoi2016] 密钥破解
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4522
数据生成器:http://paste.ubuntu.com/23140343/
这题,我觉得唯一的难点在分解因数
因为忘了棒棒糖怎么写,于是考试的时候只能写了50分的暴力
话说CQOI怎么能考模板呢?
#include<bits/stdc++.h> #define LL long long #define abs(x) ((x)>0?(x):-(x)) using namespace std; LL e,N,c,r,d,n; void EX_GCD(LL &x, LL a, LL &y, LL b) { if (!b) {x = 1; y = 0;} else {EX_GCD(y,b,x,a%b); y -= a/b*x;} } inline LL EX_GCD(LL a, LL b) { LL t1, t2; EX_GCD(t1,a,t2,b); return (t1%r + r) % r; } inline LL Mul(LL a, LL b) { LL ret = 0; while (b) { if (b&1) ret = (ret + a) % N; a = a*2 % N; b >>= 1; } return ret; } inline LL pow(LL w, LL t) { LL ret = 1; while (t) { if (t & 1) ret = Mul(ret, w); w = Mul(w, w); t >>= 1; } return ret; } inline LL GCD(LL a, LL b){ while (b) a = a % b, swap(a, b); return a; } inline void Decompose(){ for (int seed=(rand()&32767)%(N-1)+1;!r;seed=(rand()&32767)%(N-1)+1) { LL w = rand() % (N-1) + 1, seg=2, tmp = -1, cnt = 0, gcd; while (w != tmp && !r) { gcd = GCD(abs(w-tmp), N); if (1 < gcd && gcd < N) r = Mul(N/gcd-1,gcd-1); if (++cnt == seg) seg <<= 1, tmp = w; w = (Mul(w,w) + seed) % (N-1) + 1; } } } int main(){ srand(999971); cin>>e>>N>>c; Decompose(); d = EX_GCD(e,r); n = pow(c,d); cout<<d<<' '<<n; return 0; }