自建站运营,商标设计logo图案软件免费,网站专题优化,wordpress.模板正题
题目链接:https://www.luogu.com.cn/problem/P4718 题目大意
给出一个数nnn#xff0c;如果它是质数则输出PrimePrimePrime#xff0c;否则输出它的最大质因子。 解题思路 Pollard-Rho\text{Pollard-Rho}Pollard-Rho算法的前置知识是Miller-Rabin\text{Miller-Rabin}M…正题
题目链接:https://www.luogu.com.cn/problem/P4718 题目大意
给出一个数nnn如果它是质数则输出PrimePrimePrime否则输出它的最大质因子。 解题思路
Pollard-Rho\text{Pollard-Rho}Pollard-Rho算法的前置知识是Miller-Rabin\text{Miller-Rabin}Miller-Rabin。在使用Miller-Rabin\text{Miller-Rabin}Miller-Rabin判掉质数之后Pollard-Rho\text{Pollard-Rho}Pollard-Rho使用基于随机的思想能够较快的求出一个大数的因子之一。
朴素的随机算法就是随机一个数判断它是不是因子我们先使用一个较为优秀的随机方式f(x)f(x−1)2cf(x)f(x-1)^2cf(x)f(x−1)2c其中ccc为一个常数。
然后我们利用在这个函数上“跑”的距离来判断也就是每次拿某两个i,ji,ji,j判断∣f(i)−f(j)∣|f(i)-f(j)|∣f(i)−f(j)∣是否为它的因数。
但是如果枚举的话fff函数上会出现一些“环”我们需要快速的判掉“环”的方法。每次拿s,ts,ts,t令t2st2st2s若环长为ccc那么有f(x)f(xc)f(x)f(xc)f(x)f(xc)当某一时刻f(t)f(s)f(t)f(s)f(t)f(s)那么环长一定是sss的整数倍。
然后判到环就退出如果没有找到就换一个常数重新做这样的我们的算法雏形就形成了。
但是这样还是跑的很慢发现我们在过程中大量调用了gcd(d,p)gcd(d,p)gcd(d,p)导致时间变慢。考虑优化我们可以每次先做一堆然后在把这一堆拿过去一起搞定。首先我们有gcd(ac,b)gcd(a,b)gcd(ac,b)gcd(a,b)gcd(ac,b)gcd(a,b)然后根据gcdgcdgcd的原理我们有gcd(a,b)gcd(a%b,b)gcd(a,b)gcd(a\% b,b)gcd(a,b)gcd(a%b,b)那么也就是我们有gcd(a,b)gcd(ac%b,b)gcd(a,b)gcd(ac\%b,b)gcd(a,b)gcd(ac%b,b)。
那么假设我们有若干个间隔a1,a2,a3,...a_1,a_2,a_3,...a1,a2,a3,...那么我们把这数乘起来模ppp然后把得到的结果kkk与ppp取gcdgcdgcd就等价于拿aaa中逐个取与ppp取gcdgcdgcd。
所以我们的优化方法就是第iii次拿2i2^i2i个间隔去一起与ppp判断但是因为iii后面会很大导致副作用所以将iii设一个上界888即可。 时间复杂度期望是O(n2.5)O(n^{2.5})O(n2.5)但跑的飞快
回到这题来我们先对nnn用MR\text{MR}MR判断一次质数然后跑Pr\text{Pr}Pr弄出一个因子ddd之后将nnn的因子ddd都去光后分别把nnn和ddd丢下去递归继续跑。可以记录一个目前最大质因子来剪去一些不优状态。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecstdlib
#define ll long long
using namespace std;
const ll pri[10]{2,3,5,7,11,13,17,19,23,27};
ll T,n,ans;
ll ksc(ll a,ll b,ll p){ll c(long double)a*b/p;long double ansa*b-c*p;if(ans0)ansp;else if(ansp)ans-p;return ans;
}
ll power(ll x,ll b,ll p){ll ans1;while(b){if(b1)ansksc(ans,x,p);xksc(x,x,p);b1;}return ans;
}
bool Mr(ll p){if(p2)return 1;if(p2||!(p1))return 0;ll tp-1,s0;while(!(t1))t1,s;for(ll i0;i10pri[i]p;i){ll xpower(pri[i],t,p),k;for(ll j0;js;j){kksc(x,x,p);if(k1x!1x!p-1)return 0;xk;}if(x!1)return 0;}return 1;
}
ll gcd(ll a,ll b)
{return (!b)?a:gcd(b,a%b);}
ll Pr(ll p){ll s0,t0,c1ll*rand()%(p-1)1;for(ll g1,val1,d;;g1,st,val1){for(ll j0;jg;j){t(ksc(t,t,p)c)%p;valksc(val,abs(t-s),p);if(j%1270(dgcd(p,val))1)return d;}dgcd(p,val);if(d1)return d;}return p;
}
void solve(ll n){if(nans||n2)return;if(Mr(n)){ansn;return;}ll d0;while((dPr(n))n);while(n%d0)n/d;solve(n);solve(d);return;
}
signed main()
{srand(998244353);scanf(%lld,T);while(T--){scanf(%lld,n);if(Mr(n)){printf(Prime\n);continue;}ans0;solve(n);printf(%lld\n,ans);}return 0;
}
