以前我在判断素数上一直只会 sqrt(n) 复杂度的方法和所谓的试除法(预处理出sqrt(n)以内的素数,再用它们来除)。
(当然筛选法对于判断一个数是否是素数复杂度太高)
现在我发现其实还有一种方法叫做费马小定理。
有关请见 http://baike.baidu.com/link?url=1BurQrmJP3j9QiD4OnA2X3TAbSSCPvTgbaqbo6qSQPVSuXLjVe-lL2SNi6N5wblwJFrIJs41pmDbCZ6z9je4h_
代码如下:
llg ch(llg a,llg b){ //快速乘法 llg now=a,ans=0; while(b){ ) ans+=now,ans%=mod; b>>=; now<<=; now%=mod; } return ans; } bool mi(llg a,llg b){ //快速幂运算 llg s=; while(b){ ) s=ch(s,a); a=ch(a,a); b>>=; } ; } bool pd(llg x){ mod=x; ,y;i<=;i++){ y=rand()%(x-)+; )) ; } ; }
其中ch这个函数是快速乘法,可以在10^18大小的模数下相乘。
费马小定理的逆定理不一定成立,于是我们就需要多取几组加以实验。只要你人品不是太坏,就不会错。考验RP的时刻到来了
大概就是这样了吧。