线性素数筛:
1 不管 i 是不是素数, 它与素数的乘积一定不是素数, 直接 use =1;
2 如果 use=0 那么 i 是素数加入到 ss 表中, 然后枚举素数表, 执行操作 1, 如果 i 是合数, 如果素数表中有它的质因数, 则说明已经被质因数筛过了, 直接 break 即可 (我也很迷啊
- void pd()
- {
- use[1]=1;
- for(int i=2;i<=n;i++)
- {
- if(use[i]==0);
- a[++k]=i;
- for(int j=1;j<=k&&i*a[j]<=n;j++)
- {
- use[i*a[j]]=1;
- if(i%a[j]==0)
- break;
- }
- }
- return ;
- }
线性求欧拉函数:
欧拉函数性质
1: 因为欧拉函数是积性函数雾, 如果 i 与 p 互质则有 ph (i*p) =ph i *ph p i%p!=0
2:ph i*p=ph i* p i%p==0 不论 p 是不是质数
这样就可以枚举出所有情况下的欧拉函数
边线性筛边算欧拉函数:
- void get_phi()
- {
- for(int i=1;i<=N-3;i++)
- phi[i]=i;
- use[1]=1;
- for(int i=2;i<=N-3;i++)
- {
- if(use[i]==0)
- {
- ss[++k]=i;
- phi[i]=i-1;
- }
- for(int j=1;j<=k&&i*ss[j]<=N-3;j++)
- {
- int temp=i*ss[j];
- use[temp]=1;
- if(i%ss[j]==0)//i 是 ss 的倍数
- {
- phi[temp]=phi[i]*ss[j];
- break;
- }
- else
- {
- phi[temp]=phi[i]*(ss[j]-1);
- }
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3464617.html