luogu P4718 【模板】Pollard-Rho算法(贴代码)
发布时间:2020-12-14 05:15:38 所属栏目:大数据 来源:网络整理
导读:嘟嘟嘟 从标题中能看出来,我只是想贴一个代码。 先扯一会儿。 前几天模拟考到了这东西,今天有空就学了一下。 到网上找资料,发现前置技能是miller-rabin筛法,于是我还得先学这么个东西。 学miller-rabin的话不得不推荐这两篇文章: 大数质因解:浅谈Mille
嘟嘟嘟 #include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<cctype> #include<vector> #include<stack> #include<queue> #include<ctime> using namespace std; #define enter puts("") #define space putchar(‘ ‘) #define Mem(a,x) memset(a,x,sizeof(a)) #define In inline typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-8; //const int maxn = ; inline ll read() { ll ans = 0; char ch = getchar(),last = ‘ ‘; while(!isdigit(ch)) {last = ch; ch = getchar();} while(isdigit(ch)) {ans = (ans << 1) + (ans << 3) + ch - ‘0‘; ch = getchar();} if(last == ‘-‘) ans = -ans; return ans; } inline void write(ll x) { if(x < 0) x = -x,putchar(‘-‘); if(x >= 10) write(x / 10); putchar(x % 10 + ‘0‘); } ll n,Max = 0; In ll mul(ll a,ll b,ll mod) { ll d = ((long double)a / mod * b + 1e-8); //还必须是long double……double精度不够 ll r = a * b - d * mod; return r < 0 ? r + mod : r; } In ll quickpow(ll a,ll mod) { ll ret = 1; for(; b; b >>= 1,a = mul(a,a,mod)) if(b & 1) ret = mul(ret,mod); return ret; } In bool test(ll n,ll a,ll d) { ll t = quickpow(a,d,n); while(d != n - 1 && t != n - 1 && t != 1) t = mul(t,t,n),d <<= 1; return t == n - 1 || (d & 1); } int a[] = {2,3,5,7,11}; In bool miller_rabin(ll n) { if(n == 1) return 0; for(int i = 0; i < 5; ++i) //先粗筛一遍 { if(n == a[i]) return 1; if(!(n % a[i])) return 0; } ll d = n - 1; while(!(d & 1)) d >>= 1; for(int i = 1; i <= 5; ++i) //搞五遍 { ll x = rand() % (n - 2) + 2;//x属于[2,n] if(!test(n,d)) return 0; } return 1; } In ll gcd(ll a,ll b) {return b ? gcd(b,a % b) : a;} In ll f(ll x,ll mod) {return (mul(x,mod) + a) % mod;} const int M = (1 << 7) - 1; //我也不知道为啥M是这个数…… ll pollar_rho(ll n) //倍增版!减少gcd调用次数。(好像不用判环?) { for(int i = 0; i < 5; ++i) if(n % a[i] == 0) return a[i]; ll x = rand(),y = x,t = 1,a = rand() % (n - 2) + 2; for(int k = 2;; k <<= 1,y = x) { ll q = 1; for(int i = 1; i <= k; ++i) { x = f(x,n); q = mul(q,abs(x - y),n); // if(i >= M) //不等价! if(!(i & M)) //超过了2 ^ 7,再用gcd { t = gcd(q,n); if(t > 1) break; //找到了 } } if(t > 1 || (t = gcd(q,n)) > 1) break; //之所以再求一遍,是处理刚开始k < M的情况 } return t; } In void find(ll x) { if(x == 1 || x <= Max) return; if(miller_rabin(x)) {Max = max(Max,x); return;} ll p = x; while(p == x) p = pollar_rho(x); while(x % p == 0) x /= p; find(p); find(x); } int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); srand(time(0)); int T = read(); while(T--) { n = read(); Max = 0; find(n); if(Max == n) puts("Prime"); else write(Max),enter; } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |