定义
若f(x)满足f(pq)=f(p)*f(q)且p⊥q，则f(x)为积性函数。
特殊地，若不要求p⊥q，则为完全积性函数。
性质一
若将n表示成质因子分解式
则有：
性质二
若f为积性函数且有 
暴力筛
暴力出奇迹。
埃氏筛
思路就是找到一个素数后筛掉它的所有倍数。
欧拉筛
相当于埃氏筛的一个优化，即只用一个合数的最小质因数筛，避免重复筛。
const int M=1e8+8; int prime[M],cnt;//素数表 bool ss[M];//i是否是素数 inline void sushu(){ memset(ss,true,sizeof(ss)); for(int i=2;i<=M;i++){ if(ss[i]) prime[++cnt]=i; for(int j=1;j<=cnt;j++){ if(i*prime[j]>M||(!i%prime[j])) break;//筛完结束&避免重复筛 ss[i*prime[j]]=false; } } ss[1]=ss[0]=false; }
MIller-Rabin筛素数
看到数据范围就晓得要用了。
inline ll ksm(ll a,ll b,ll mo){ ll ans=1; while(b){ if(b&1) ans*=a%mo; a*=a%mo; b>>=1; } return ans; } inline bool check(ll x,ll y,ll p){//二次探测 ll tmp=ksm(x,y,p); if(tmp!=1&&tmp!=p-1) return false; if(tmp==p-1||(tmp==1&&(y&1))) return true; return check(x,y>>1,p); } inline bool millerrabin(ll x){ if(x<=1) retunr false; if(x==2||x==7||x==61||(check(2,x-1,x)&&check(7,x-1,x)&&check(61,x-1,x))) return true; return false; }
放个链接。Pollard-Rho。下辈子考吧。
原文：https://www.cnblogs.com/jian-song/p/11619199.html
