Warning: session_start(): open(/tmp/sess_7fb1274baac5c63aa25d618b0343070d, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/8/8fe637ac40e9dfa91f93fbcd08d065e4.captchaip failed

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:namespace:pollardrho算法板子 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:namespace:pollardrho算法板子

点击以显示 ⇲

点击以隐藏 ⇱

long long f(long long x,long long c,long long n)
{
	return ((long long)x*x+c)%n;
}
 
long long PollardRho(long long x)
{
	long long s=0,t=0;
	long long c=rand()%(x-1)+1;
	long long val=1;
	int goal; 
	for(goal=1;;goal<<=1,s=t,val=1)
	{
		int step;
		for(step=1;step<=goal;++step)
		{
			t=f(t,c,x);
			val=val*abs(t-s)%x;
			if((step%127)==0)
			{
				long long d=gcd(val,x);
				if(d>1)
				{
					return d;
				}
			}
		}
		long long d=gcd(val,x);
		if(d>1)
		{
			return d;
		}
	}
}
2020-2021/teams/namespace/pollardrho算法板子.txt · 最后更改: 2021/01/28 12:22 由 great_designer