线性筛素数欧拉函数莫比乌斯函数

判断素数：对于n，分别枚举1-sqrt（n）。

最朴素的素数筛——埃拉托斯特尼筛法(Sieve of Eratosthenes)

 1 int primes[MAXN],ent=0;
 2 bool isPrime[MAXN];
 3 void getPrime()
 4 {
 5     memset(isPrime,true,sizeof(isPrime));
 6     for(int i=2;i<MAXN;i++)
 7     {
 8         if(isPrime[i])
 9         {
10             primes[++ent]=i;
11             for(int j=i+i;j<MAXN;j+=i)
12                 isPrime[j]=false;
13         }
14     }
15 }

复杂度：nlglgn

欧拉筛：每个合数只会被一个素数筛去，所以复杂度线性。

原理：每个比 i 大的合数，必可以拆分为一个比 i 小的质数和另一个合数之积

 1 int primes[MAXN],tot=0;
 2 bool isPrime[MAXN];
 3 
 4 void getPrime()
 5 {
 6     memset(isPrime,true,sizeof(isPrime));
 7     for(int i=2;i<MAXN;i++)
 8     {
 9         if(isPrime[i])
10             primes[++tot]=i;
11         for(int j=1;j<=tot;j++)
12         {
13             if(i*primes[j]>=MAXN) break;
14             isPrime[i*primes[j]]=false;
15             if(i%primes[j]==0) break;//就这
16         }
17     }
18 ————————————————

积性函数：f(ab)=f(a)f(b).ab不要求互素为完全积性函数。

·欧拉函数

·莫比乌斯函数

欧拉函数(积性函数)

欧拉函数 ϕ(n) 是小于或等于n的正整数中与n互质的数的数目。

定义式：ϕ(n)=n(1−1/p1)(1−1/p2)…(1−1/pk),p1…pk是n的k个不同的质因数。

一些性质：

ϕ(n*p)=ϕ(n)*p. p为素数（照定义式一写可证）

ϕ(p)=p-1.

可得代码

 1 int tot=0;
 2 int phi[maxn],prime[maxn];
 3 bool isPrime[maxn];
 4 void getphi(){
 5     memset(isPrime,true,sizeof(IsPrime));
 6     phi[1]=1;
 7     for(int i=2;i<=maxn;i++){
 8         if(isPrime[i]) prime[++tot]=i,phi[i]=i-1;//*
 9         for(int j=1;j<=tot;j++){
10             if(i*prime[j]>maxn) break;
11             isPrime[i*prime[j]]=false;
12             if(i%prime[j]==0){
13                 phi[i*prime[j]]=phi[i]*prime[j];//*
14                 break;
15             }else phi[i*prime[j]]=phi[i]*(prime[j]-1);//*
16         }
17     }
18 }

莫比乌斯函数

莫比乌斯函数μ(d)的定义如下
(1)若d=1，那么μ(d)=1
(2)若d=p1p2…pk(p1…pk均为互异质数)，那么μ(d)=(−1)^k
(3)其他情况下，μ(d)=0

假设当前从μ(i),μ(p)转移到μ(i·p)，
1、如果p是在ip中第一次出现的话(也就是p不整除i)，则μ(i·p)=−μ(i)
2、如果p不是在ip中第一次出现的话(也就是p整除i)，则μ(i·p)=0

 1 int tot=0;
 2 int mu[maxn],prime[maxn];
 3 bool isPrime[maxn];
 4 void getmiu(){
 5     memset(isPrime,true,sizeof(isPrime));
 6     mu[1]=1;
 7     for(int i=2;i<=maxn;i++){
 8         if(isPrime[i]) prime[++tot]=i,mu[i]=-1;
 9         for(int j=1;j<=tot;j++){
10             if(i*prime[j]>maxn) break;
11             isPrime[i*prime[j]]=false;
12             if(i%prime[j]==0){
13                 mu[i*prime[j]]=0;
14                 break;
15             }else miu[i*prime[j]]=-1*mu[i];
16         }
17     }
18 }

莫比乌斯反演

F(n),f(n) 是定义在非负整数集合上的两个函数，并且满足条件
$这里写图片描述$

则

似乎有一个绝妙的性质：

example：

1.求(i,j)=x的个数

还没写完，回头再补。挂个参考链接，如有侵权立删。

https://blog.csdn.net/qq_30115697/article/details/89219146

线性筛素数 欧拉函数 莫比乌斯函数

1.求(i,j)=x的个数

线性筛素数欧拉函数莫比乌斯函数