【BZOJ 4522】【CQOI 2016】密钥破解

3/8/2017来源:ASP.NET技巧人气:3095

其实这道题目的核心就是把N分解质因数。

引用一个很玄学的算法:pollard_rho算法。 http://blog.csdn.net/maxichu/article/details/45459533

代码如下。玄学之处有两个,一个是每次平方加上一个常数(这里是seed),第二个是每次达到上限k就重新开始,并且k的范围乘2。 分解完质因数就是解一个类似于ax+by=1的方程,套一下裴蜀和扩展欧几里得即可。

ll Pollard_Rho(ll n) { ll x,y,cnt = 1,k = 2; x = rand() % (n-1) + 1; y = x; while (1) { cnt++; x = (Quick_mul(x,x,n) + seed) % n; ll gcd = Get_gcd(abs(x-y),n); if (1 < gcd && gcd < n) return gcd; if (x == y) return n; //本来是如果出现环就重新计算 if (cnt == k) y = x,k = k << 1; //扩大上限 } } //...// srand(seed); p = Pollard_Rho(N); while (p == N) p = Pollard_Rho(N);

更加玄学的是,网上有一份AC代码,取seed=10007,在不加while循环的情况下一次分解成功(正常情况下要多次),而且这份代码是过不了样例的。。。

PS:该算法由一个叫Pollard的人提出(好像是的),因为每次一定会产生循环,形似希腊字母ρ,故得名。

#include<cmath> #include<cstdio> #include<vector> #include <queue> #include<cstring> #include<iomanip> #include<stdlib.h> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define mod 1000000007 #define seed 233333 #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) using namespace std; ll e,N,c,p,q,r,d; ll Quick_mul(ll x,ll y,ll p) //快速加x+y { ll i,res = 0; for (i = y;i > 0; i = i >> 1,x = (x + x) % p) if (i & 1) res = (res + x) % p; return res; } ll Quick_pow(ll x,ll y,ll p) //快速幂x^y { ll i,res = 1; for (i = y;i > 0; i = i >> 1,x = Quick_mul(x,x,p)) if (i & 1) res = Quick_mul(res,x,p); return res; } void Exgcd(ll a,ll b,ll &x,ll &y) //ax+by=1 { if (b == 0) {x = 1; y = 0; return;} Exgcd(b,a%b,y,x); y = y - (a / b) * x; } ll Get_inv(ll n,ll p) { ll x,y; Exgcd(n,p,x,y); return (x % p + p) % p; } ll Get_gcd(ll a,ll b) { if (b == 0) return a; return Get_gcd(b,a%b); } ll Pollard_Rho(ll n) { ll x,y,cnt = 1,k = 2; x = rand() % (n-1) + 1; y = x; while (1) { cnt++; x = (Quick_mul(x,x,n) + seed) % n; ll gcd = Get_gcd(abs(x-y),n); if (1 < gcd && gcd < n) return gcd; if (x == y) return n; //本来是如果出现环就重新计算 if (cnt == k) y = x,k = k << 1; //扩大上限 } } int main() { srand(seed); cin>>e>>N>>c; p = Pollard_Rho(N); while (p == N) p = Pollard_Rho(N); q = N / p; r = (p - 1) * (q - 1); d = Get_inv(e,r); //Exgcd求逆元 PRintf("%lld %lld\n",d,Quick_pow(c,d,N)); return 0; }