A234题解-建议升紫

思路

这题一眼 Pollard-Rho 好吧，一看数据范围和有人枚举 TLE 就上 PR 了。

Pollard-Rho 板子

期望时间复杂度：$O(n^{\frac{1}{4}})$

代码

PR 板子，不多说。

int qpow(int a,int k,int mod)
{
	a%=mod;
	int res=1;
	while(k)
	{
		if(k&1)res=res*a%mod;
		a=a*a%mod;
		k>>=1;
	}
	return res;
}
int p[12]={2,3,5,7,11,13,17,19,23,29,31,37};
bool millerrabin(int n)
{
	if(n<=2)return n==2;
	if(n<=37)
	{
		for(int i=0;i<12;i++)
		{
			if(n==p[i])return 1;
		}
		return 0;
	}
	int u=n-1,t=0;
	while(u%2==0)u/=2,t++;
	for(int i=0;i<12;i++)
	{
		int v=qpow(p[i],u,n);
		if(v==1)continue;
		int s=0;
		for(;s<t;s++)
		{
			if(v==n-1)break;
			v=(v*v)%n;
		}
		if(s==t)return 0;
	}
	return 1;
}
 int pr(int n)
{
	int y=0,x=0,c=rand()%(n-1)+1,j=0,i,v=1;
	for(i=1;;i<<=1,y=x,v=1)
	{
		for(j=1;j<=i;j++)
		{
			x=((int)x*x+c)%n;
			v=((int)v*(x>y?x-y:y-x))%n;
			if(j%127==0)
			{
				int d=__gcd(v,n);
				if(d>1)return d;
			}
		}
		int d=__gcd(v,n);
		if(d>1)return d;
	}
}
__int128 read()
{
	__int128 x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
void print(__int128 x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)print(x/10);
	putchar(x%10+'0');
}
int maxn;
void dfs(int n)
{
	if(n<=maxn||n<2)return ;
	if(millerrabin(n))
	{
		maxn=max(maxn,n);
		return ;
	}
	int P=n;
	while(P>=n)P=pr(P);
	while(n%P==0)n/=P;
	dfs(P);
	dfs(n);
}
int T,n;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//srand(time(NULL));
	//cin>>T;
	//T=read();
    T=1;
	while(T--)
	{
		//cin>>n;
		n=read();
		maxn=INT_MIN;
		if(millerrabin(n))
		{
			puts("Prime");
			continue;
		}
		dfs(n);
		//cout<<maxn<<endl;
		print(maxn);
		putchar('\n');
	}
	return 0;
}

核弹打蚊子