【模板】埃拉托色尼筛法 && 欧拉筛法 && 积性函数

埃拉托色尼筛法

　　朴素算法

1 vis[1]=1;
2 for (int i=2;i<=n;i++)
3     if (!vis[i])
4     {
5         pri[++tot]=i;
6         for (int j=i*2;j<=n;j+=i)
7             vis[j]=1;
8     }

欧拉筛法

　　朴素算法

 1 vis[1]=1;
 2 for (int i=2;i<=n;i++)
 3 {
 4     if (!vis[i])
 5         pri[++tot]=i;
 6     for (int j=1;j<=tot;j++)
 7     {
 8         if (i*pri[j]>n) break;
 9         vis[i*pri[j]]=1;
10         if (i%pri[j]==0) break;
11     }
12 }

以luoguP3383为例

标程：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int prime[10000020],mark[10000020];
 4 int bj,ph[10000020];
 5 void oula(int p){
 6     ph[1]=1;
 7     for(int i=2;i<=p;i++) {
 8         if(!mark[i]){
 9             prime[++bj] = i;
10             ph[i]=i-1;
11         }
12         for(int j=1;j<=bj;j++){
13             if(i*prime[j]>p) break;
14             mark[i*prime[j]]=1;
15             if(i%prime[j]==0)    {
16                 ph[i*prime[j]]=ph[i]*prime[j];
17                 break;
18             }
19             else ph[i*prime[j]]=ph[i]*ph[prime[j]];
20         }
21     }
22 }
23 int n,m1;
24 int main(){
25     cin>>n>>m1;
26     oula(n);
27     for(int i=1;i<=m1;i++)  {
28         int m;
29         cin>>m;
30         if(m-1!=ph[m]) cout<<"No"<<endl;
31         else cout<<"Yes"<<endl;
32     }
33     return 0;
34 }

以下内容为转载于https://blog.csdn.net/y20070316/article/details/51729812

二. 欧拉筛法解积性函数

1. 方法

步骤Ⅰ：证明积性 
步骤Ⅱ：考虑下面三方面的实现： 
①素数m，求f(m) 
②m和比m的最小素因子小的素数n，求f(n*m) 
③m和m的最小素因子n：求f(n*m)

2. 例子

（1）欧拉函数

题目：PC 1499

证明：设[Math Processing Error]n=∏aipi，m=∏biqi，且[Math Processing Error]gcd(m,n)=1 
[Math Processing Error]∴ϕ(mn)=mn∏(1−1ai)∏(1−1bi)=[n∗∏(1−1ai)]∗[m∗(∏(1−1bi)]=ϕ(n)ϕ(m)

写法： 
①素数m：[Math Processing Error]ϕ(m)=m−1 
②m和比m的最小素因子小的素数n： 
[Math Processing Error]ϕ(m∗n)=ϕ(m)∗phi(n) 
③m和m的最小素因子n：[Math Processing Error]ϕ(m∗n)=ϕ(m)∗n

 1 phi[1]=1;
 2 for (int i=2;i<=n;i++)
 3 {
 4     if (!phi[i])
 5     {
 6         pri[++tot]=i;
 7         phi[i]=i-1;
 8     }
 9     for (int j=1;j<=tot;j++)
10     {
11         if (i*pri[j]>n) break;
12         if (i%pri[j]!=0)
13             phi[i*pri[j]]=phi[i]*phi[pri[j]];
14         else
15         {
16             phi[i*pri[j]]=phi[i]*pri[j];
17             break;
18         }
19     }
20 }
（2）莫比乌斯函数

题目：PC 1492

积性证明： 
设[Math Processing Error]n=∏aipi，m=∏biqi，且[Math Processing Error]gcd(m,n)=1 
①若[Math Processing Error]∃pi>1或[Math Processing Error]qi>1，则[Math Processing Error]μ(n∗m)=μ(n)∗μ(m)=0 
②否则，[Math Processing Error]μ(n∗m)=(−1)n+m=μ(n)∗μ(m) 
综上，[Math Processing Error]μ(n∗m)=μ(n)∗μ(m)

写法： 
①素数m：[Math Processing Error]μ(m)=−1 
②m和比m的最小素因子小的素数n： 
[Math Processing Error]μ(m∗n)=μ(m)∗μ(n) 
③m和m的最小素因子n：[Math Processing Error]μ(n∗m)=0

 1 mu[1]=vis[1]=1;
 2 for (int i=2;i<=n;i++)
 3 {
 4     if (!vis[i])
 5     {
 6         mu[i]=-1;
 7         pri[++tot]=i;
 8     }
 9     for (int j=1;j<=tot;j++)
10     {
11         if (i*pri[j]>n) break;
12         vis[i*pri[j]]=1;
13         if (i%pri[j]!=0)
14             mu[i*pri[j]]=mu[i]*mu[pri[j]];
15         else
16         {
17             mu[i*pri[j]]=0;
18             break;
19         }
20     }
21 }
（3） 乘法逆元[Math Processing Error]inv(n,i)([Math Processing Error]n不变)

题目：PC 1494

积性证明： 
[Math Processing Error]∵a∗inv[a]≡1,b∗inv[b]≡1(modn) 
[Math Processing Error]∴(a∗b)∗(inv[a]∗inv[b])≡1(modn) 
[Math Processing Error]∴inv[a∗b]≡inv[a]∗inv[b]

写法： 
①素数m：根据费马小定理，[Math Processing Error]inv[m]≡Pow(m,n−2) 
②m和比m的最小素因子小的素数n：[Math Processing Error]inv[m∗n]=inv[m]∗inv[n] 
③m和m的最小质因子n： 
根据完全积性，[Math Processing Error]inv[m∗n]=inv[m]∗inv[n]

注意，第①步是[Math Processing Error]O(n)的。这是因为： 
[Math Processing Error]O(π(n)log⁡n)=O(nln⁡nlog⁡n)=O(nlog⁡nlog⁡n)=O(n)。

 1 vis[1]=inv[1]=1;
 2 for (int i=2;i<n;i++)
 3 {
 4     if (!vis[i])
 5     {
 6         pri[++tot]=i;
 7         inv[i]=Pow(i,n-2);
 8     }
 9     for (int j=1;j<=tot;j++)
10     {
11         if (i*pri[j]>n) break;
12         vis[i*pri[j]]=1;
13         inv[i*pri[j]]=inv[i]*inv[pri[j]];
14         if (i%pri[j]==0) break;
15     }
16 }

其实可以直接有一种递推的方法： 
①当n=1时，inv[n]=1 
②假设当前对于k，已经求出了inv[1]，inv[2]，…，inv[k-1]，当前要求出inv[k]。 
令[Math Processing Error]a=nmodk，[Math Processing Error]b=n/k 
[Math Processing Error]∴n=a+b∗k 
[Math Processing Error]∴a=n−b∗k 
又[Math Processing Error]∵inv[a]∗a≡inv[a]∗(n−b∗k)≡inv[a]∗−b∗k≡1 
[Math Processing Error]∴inv[k]=−b∗inv[a]

（4）最大公约数[Math Processing Error]gcd(a,b)(b一定)

题目：PC 1495

证明：略

写法：求[Math Processing Error]g(i) 
①素数m：[Math Processing Error]g(m)=gcd(m,b)； 
②m和比m的最小素因子小的素数n： 
[Math Processing Error]g(m∗n)=g(m)∗g(n)； 
③m和m的最小质因子n： 
设[Math Processing Error]ek(m)表示n的最大的幂，满足[Math Processing Error]ek(m)|m 
若[Math Processing Error](ek(m)∗n)|b，则[Math Processing Error]g(m∗n)=g(m)∗n 
若不满足，则[Math Processing Error]g(m∗n)=g(m)；

[Math Processing Error]ek(i)不是积性函数，但也可以放在欧拉筛法里面求： 
①素数m：[Math Processing Error]ek(m)=m 
②m和比m的最小素因子小的素数n：[Math Processing Error]ek(m∗n)=n 
③m和m的最小质因子n：[Math Processing Error]ek(m∗n)=ek(m)∗n

（5）正因子数目[Math Processing Error]d(n)

题目：PC 1496

证明： 
设[Math Processing Error]m=∏aipi，[Math Processing Error]n=∏biqi且[Math Processing Error]m,n互质 
[Math Processing Error]∴d(mn)=d(∏aipi∏biqi)=∏(pi−1)∏(qi−1)=d(m)∗d(n)

求法：求[Math Processing Error]d(i) 
①素数m：[Math Processing Error]d(m)=2 
②m和比m的最小素因子小的素数n：[Math Processing Error]d(m∗n)=d(m)∗d(n) 
③m和m的最小质因子n： 
[Math Processing Error]d(m∗n)=d(m)/(e(m)+1)∗(e(m∗m)+1)，[Math Processing Error]e(m)表示最大的满足[Math Processing Error]ne(m)|m的值。

求[Math Processing Error]e(i)： 
①素数m：[Math Processing Error]e(m)=1 
②m和比m的最小素因子小的素数n：[Math Processing Error]e(m∗n)=1 
③m和m的最小质因子n：[Math Processing Error]e(m∗n)=e(m)+1

（6）正因子之和[Math Processing Error]s(n)

题目：PC 1497

证明： 
设[Math Processing Error]m=∏aipi，[Math Processing Error]n=∏biqi且[Math Processing Error]m,n互质, 
则[Math Processing Error]s(m∗n)=∏j(∑j=0piaij)∗∏j(∑j=0qibij)=s(m)s(n)

写法： 
①素数m：[Math Processing Error]s(m)=m+1 
②m和比m的最小素因子小的素数n：[Math Processing Error]s(m∗n)=s(m)∗s(n) 
③m和最小质因数n： 
[Math Processing Error]s(m∗n)=s(∏aipi∗ne(i)+1)=∏(∑j=0piaij)∗(∑j=0e(i)+1nj)=s(m)∗(∑j=0e(i)+1nj)(∑j=0e(i)nj)=s(m)∗ne(i)+2−1n−1∗n−1ne(i)+1−1=s(m)∗ne(i)+2−1ne(i)+1−1

记[Math Processing Error]pe(m)=ne(i)+1，则可以在欧拉筛法的同时求出。

（8）另一些显而易见的积性函数

1(n)：1(n)=1，完全积性 
Id(n)：Id(n)=n，完全积性 
Idk(n)：Idk(n)=n^k，完全积性

3. 实现技巧

（1）节省空间

很多时候，有些数组A可以当作另外一些数组B的功能拓展，这时候就可以把B省略掉。

例如，在求欧拉函数的时候，我们可以用phi来取代vis数组。因为没有求出来的phi(i)也就意味着i是素数。

又例如，在求莫比乌斯函数的时候，我们可以用mu来取代vis数组。理由同上。不过要把mu数组的初始值设为-1。

（2）模板

变量：

  • 布尔数组vis[N]
  • 素数表pri[N],tot
  • 积性函数

模板：

 1 void solve(void)
 2 {
 3     vis[1]=...=1;   //赋初始值 
 4     for (int i=2;i<=n;i++)
 5     {
 6         if (!vis[i])
 7         {
 8             ...             //素数的积性函数值
 9             pri[++tot]=i;   //加入素数表 
10         }
11         for (int j=1;j<=tot;j++)
12         {
13             if (i*pri[j]>n) break;
14             vis[i*pri[j]]=1;
15             ...                 //公共部分
16             if (i%pri[j]!=0)
17             {
18                 ...             //m和比m的最小素因子小的素数n的处理 
19             }
20             else
21             {
22                 ...             //m和m的最小素因子n的处理 
23                 break;
24             }
25         } 
26     } 
27 }

4. 变式

（1）“加性”函数

例题：PC 1498 
有些涉及到素因子的函数，也可以使用欧拉筛法求解。很多时候可以辅助积性函数的求解，上面的例子中的[Math Processing Error]e函数，[Math Processing Error]ek函数就是所谓的“加性”函数。

（2）[Math Processing Error]A2

例题：XSY 1001 
对于[Math Processing Error]A2的积性函数，关键求出[Math Processing Error]A的积性函数，然后顺便求解[Math Processing Error]A2的积性函数。

（3）[Math Processing Error](A+1)(A−1)

例题：XSY 1001 
通常一个乘积的形式，也可以通过互质的关系，转化为有关积性函数的问题。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/luv-letters/p/9338355.html