RT

这两份代码

ll Pollardrho(ll x)
{
	if(x==4) return 2;
	while(1)
	{
		ll c=(ll)rand()%(x-1)+1;
	    ll t=0,r=0,p=1,q;
	    int step,goal=1;
	    bool flag=0;
	    for(;;goal<<=1)
	    {
	    	for(step=1;step<=goal;step++)
	    	{
	    		t=f(t,c,x),r=f(f(r,c,x),c,x);
	    		q=(__int128)p*abs(t-r)%x;
	    		if(t==r||!q) 
	    		{
	    			flag=1;
	    			break;
				}
	    		p=q;
	    		if(step%127==0){
	    			ll d=gcd(p,x);
			        if(d>1) return d;
				}
			}
			ll d=gcd(p,x);
			if(d>1) return d;
			if(flag) break;
		}
	}
}

ll Pollardrho(ll x)
{
	if(x==4) return 2;
	while(1)
	{
		ll c=rand()%(x-1)+1;
	    ll t=0,r=0,p=1,q;
	    do{
	    	for(int i=1;i<=128;i++)
	    	{
	    		t=f(t,c,x),r=f(f(r,c,x),c,x);
	    		q=(__int128)p*abs(t-r)%x;
	    		if(t==r||!q) break;
	    		p=q;
			}
			ll d=gcd(p,x);
			if(d>1) return d;
		}while(t!=r);
	}
}

第一份是倍增优化，第二份是进行了优化的floyd优化

实际测试中，两者都AC且运行速度差不多，但第二份代码确实存在中途某次gcd满足条件，但是128次之后累乘就变成了0的问题，但是为什么还能AC呢？或者说这个本身影响不大，因为有重新判断，只是可能稍微增加运行时间？