【模板】Pollard-Pho算法【牛客tracker 每日一题】

【模板】Pollard-Pho算法时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述判断一个正整数x xx是否是质数。特别的这个x xx可能很大。输入描述本题每组输入包含多组测试用例。输入的第一行包含一个正整数T 1 ≦ T ≦ 10 5 T1≦T≦10^5T1≦T≦105测试用例数。接下来T TT行每行一个正整数x 1 ≦ x ≦ 10 12 x1≦x≦10^{12}x1≦x≦1012表示需要判定是否是质数的数。输出描述对于每组测试用例如果对应的x xx为质数输出Y e s YesYes否则输出N o NoNo。示例1输入4 1000000007 998244353 114514 7输出Yes Yes No Yes解题思路本题是大整数素性判定模板题数值范围可达10 12 10^{12}1012采用Miller-Rabin 素性测试算法高效求解。该算法基于费马小定理与二次探测定理通过多轮概率测试可实现指定范围内的确定性素数判定远优于试除法的效率。算法核心原理对于奇素数n nn可将n − 1 n-1n−1分解为d × 2 s d \times 2^sd×2sd dd为奇数。任选底数a aa若a d ≡ 1 ( m o d n ) a^d \equiv 1 \pmod nad≡1(modn)或存在0 ≤ r s 0 \le r s0≤rs使得a d × 2 r ≡ − 1 ( m o d n ) a^{d \times 2^r} \equiv -1 \pmod nad×2r≡−1(modn)则n nn通过本轮素性测试。选择固定小质数集合作为底数在10 12 10^{12}1012范围内可实现 100% 准确的判定。具体执行步骤边界预处理小于 2 直接判定为非素数2、3 直接判定为素数所有偶数直接排除。分解指数将n − 1 n-1n−1不断除以 2得到奇数d dd即n − 1 d × 2 s n-1 d \times 2^sn−1d×2s。多轮测试选取底数集合{2,3,5,7,11,13,17,19,23,29,31,37}对每个底数执行完整测试计算a d m o d n a^d \bmod nadmodn若结果既不是 1 也不是n − 1 n-1n−1则反复平方进行二次探测若始终无法得到n − 1 n-1n−1则判定为合数。结果输出所有底数测试通过则判定为素数否则为合数。大整数乘法通过__int128实现避免 64 位整数相乘溢出。单个数判定的时间复杂度为O ( k log ⁡ n ) O(k\log n)O(klogn)k kk为底数个数可轻松应对十万级测试用例。总结核心逻辑基于数论定理的 Miller-Rabin 素性测试通过固定底数集合实现万亿级数值的确定性素数判定。关键操作分解n − 1 n-1n−1为奇因子乘 2 的幂、快速幂模运算、二次探测校验、__int128处理大数乘法防溢出。效率保障常数轮测试 对数级运算量无冗余计算完美适配大数据量与大数值范围。代码简要说明快速幂函数pmod实现模意义下的快速幂运算乘法步骤使用__int128强制转换彻底解决大整数相乘溢出问题保证运算正确性。素性判定函数isp处理边界情况小数值、偶数快速返回结果。分解n − 1 n-1n−1为奇数d dd剥离所有 2 的因子。遍历固定底数集合逐轮执行 Miller-Rabin 测试任意一轮不通过则直接判定为合数。全部测试通过则判定为素数。主函数逻辑关闭同步流加速输入输出读取T TT组测试用例逐个调用素性判定函数按要求输出Yes或No。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;llpmod(ll a,ll b,ll md){ll r1;a%md;while(b0){if(b1)r(__int128)r*a%md;a(__int128)a*a%md;b1;}returnr;}boolmrchk(ll d,ll n){ll a2rand()%(n-4);ll xpmod(a,d,n);if(x1||xn-1)returntrue;while(d!n-1){x(__int128)x*x%n;d*2;if(x1)returnfalse;if(xn-1)returntrue;}returnfalse;}boolisp(ll n){if(n2)returnfalse;if(n2||n3)returntrue;if(n%20)returnfalse;ll bs[]{2,3,5,7,11,13,17,19,23,29,31,37};ll dn-1;while(d%20)d/2;for(ll a:bs){if(na)returntrue;if(pmod(a,d,n)!1){ll td;boolokfalse;while(tn-1){if(pmod(a,t,n)n-1){oktrue;break;}t*2;}if(!ok)returnfalse;}}returntrue;}voidsol(){ll x;cinx;cout(isp(x)?Yes:No)endl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T;cinT;while(T--)sol();return0;}