• 欢迎光临~

P4718 【模板】Pollard-Rho算法

开发技术 开发技术 2022-10-27 次浏览

题目链接

P4718 【模板】Pollard-Rho算法

题目描述

Miller Rabin 算法是一种高效的质数判断方法。虽然是一种不确定的质数判断法,但是在选择多种底数的情况下,正确率是可以接受的。

Pollard Rho是一个非常玄学的方式,用于在(O(n^{1/4}))的期望时间复杂度内计算合数n的某个非平凡因子。事实上算法导论给出的是(O(sqrt p))(p)(n)的某个最小因子,满足(p)(n/p)互质。但是这些都是期望,未必符合实际。但事实上Pollard Rho算法在实际环境中运行的相当不错。

这里我们要写一个程序,对于每个数字检验是否是质数,是质数就输出Prime;如果不是质数,输出它最大的质因子是哪个。

输入格式

第一行,(T)代表数据组数(不大于(350)

以下(T)行,每行一个整数(n),保证(1 < nle 10^{18})

输出格式

输出(T)行。

对于每组测试数据输出结果。

样例 #1

样例输入 #1

6
2
13
134
8897
1234567654321
1000000000000

样例输出 #1

Prime
Prime
67
41
4649
5

解题思路

pollard_rho

pollard_rho 算法可以较快求出 (n) 的一个非平凡因子(即不包括 (1) 和本身),主要在于随机找到这样的 (x),使得 (d=gcd(x,n)),如果 (1< d< n)(d) 即为所求,(color{red}{如何快速这样的 x 呢?})首先需要引入生日悖论,即至少有 (23) 人能使两个人生日相同的概率达到 (50%),不妨构造这样一个伪随机函数 (f(x)=(x^2+c)bmod n),其生成一个随机数序列 ({x_i}),由生日悖论,这样的不同值的数量有 (O(sqrt{n})) 个,设 (m)(n) 的最小非平凡因子((mleq sqrt{n})),记 (y_i=x_i(bmod m)),推导如下:

[y_{i+1}=x_{i+1} bmod m\ =left(x_i^2+c bmod nright) bmod m\ =left(x_i^2+cright) bmod m\ =left(left(x_i bmod mright)^2+cright) bmod \ =y_i^2+c quad(bmod m) ]

故其也会生成一个 ({y_i}) 序列,数量为 (O(m)),由赛跑原则,即两人同时同地跑步,速度不同,最终两个相遇时相差的距离一定是整个跑道长度的整数倍。现在需要找到一个不同的 (i,j),使得 (x_ineq x_j&&y_i= y_j),时间复杂度为 (O(sqrt{m})) 时有大概 (frac{1}{2}) 的概率这样的 (i,j),故:

  • 时间复杂度:(O(m)=O(n^{frac{1}{4}}))

代码

// Problem: P4718 【模板】Pollard-Rho算法
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4718
// Memory Limit: 125 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int test_time=20;
int t;
LL n,res;
LL ksm(LL a,LL b,LL p)
{
	LL res=1%p;
	while(b)
	{
		if(b&1)res=(__int128)res*a%p;
		a=(__int128)a*a%p;
		b>>=1;
	}
	return res;
}
bool miller_rabin(LL n)
{
	if(n<3||n%2==0)return n==2;
	LL a=n-1,b=0;
	while(a%2==0)a>>=1,b++;
	for(int i=1,j;i<=test_time;i++)
	{
		LL x=rand()%(n-2)+2,v=ksm(x,a,n);
		if(v==1)continue;
		for(j=0;j<b;j++)
		{
			if(v==n-1)break;
			v=(__int128)v*v%n;
		}
		if(j>=b)return false;
	}
	return true;
}
LL pollard_rho(LL x)
{
	LL s=0,t=0;
	LL c=(LL)rand()%(x-1)+1;
	int i=1,j=0;
	LL v=1;
	for(i=1;;i<<=1,s=t,v=1)
	{
		for(int j=1;j<=i;j++)
		{
			t=((__int128)t*t+c)%x;
			v=(__int128)v*abs(t-s)%x;
			if(j%127==0)
			{
				LL d=__gcd(v,x);
				if(d>1)return d;
			}
		}
		LL d=__gcd(v,x);
		if(d>1)return d;
	}
}
void fac(LL x)
{
	if(x<=res||x<2)return ;
	if(miller_rabin(x))
	{
		res=max(res,x);
		return ;
	}
	LL p=x;
	while(p>=x)p=pollard_rho(p);
	while(x%p==0)x/=p;
	fac(x),fac(p);
}
int main()
{
    for(scanf("%d",&t);t;t--)
    {
    	res=0;
    	srand(time(0));
    	scanf("%lld",&n);
    	fac(n);
    	if(res==n)puts("Prime");
    	else
    		printf("%lldn",res);
    }
    return 0;
}
程序员灯塔
转载请注明原文链接:P4718 【模板】Pollard-Rho算法
喜欢 (0)