线性筛欧拉函数学习笔记

我回来了，在被模板蹂躏之后。

预先规定：

• \(s_i\) 表示筛出的第 \(i\) 个质数。
• \(p_i\) 表示数字 \(i\) 的欧拉函数值，即 \(\varphi(i)\)。
• \(f_i\) 表示数字 \(i\) 的最小质因数。

筛法

参考筛素数的线性筛，当筛到数字 \(i\) 时，小于 \(i\) 的数的欧拉函数和小于 \(i\) 的质数已经筛出，利用 \(i\) 和 \(s\) 向后更新。

对于数字 \(i\)，如果此时 \(f_i=0\)，说明这个数的最小质因数不会在 \(\left[2,i-1\right]\) 的范围内出现，也易得数字 \(i\) 是个质数，根据前一篇博客中写到的欧拉函数性质可知，此时 \(\varphi(i)=i-1\)

所以，如果数字 \(i\) 为质数：

1. 将 \(i\) 加入筛出的素数表。
2. \(f_i=i\)，质数的最小质因数是自身。
3. 更新 \(p_i\) 的值为 \(i-1\)。

接下来，无论 \(i\) 是否为质数，直接在素数表中枚举 \(s_j\)。

• 如果 \(i \bmod s_j!=0\)，可知 \((i,s_j)=1\)，此时有 $$p_{i \times s_j} = p_i \times p_{s_j} = p_i \times (s_j - 1)$$
• 如果 \(i \bmod s_j=0\)，此时 $$p_{i \times s_j} = p_i \times s_j$$
• 同时更新 $$f_{s_j \times i} = s_j$$

证明

有两种证明方法，一种是推论，另一种是通式。

推论法

\(i \bmod s_j=0\) 时无法直接计算的原因是两个数不互质。
假设 $$i \times p_j = A \times p_j^{m-1} \times p_j = p_j^m$$
之前那篇笔记已经解释过，若 \(x\) 是质数，\(\varphi(x^k) = x^k-x^{k-1}\)
因为 $$\varphi(i \times p_j) = \varphi(A) \times \varphi(p_j^m) = \varphi(A) \times \varphi(p_j^{m-1}) \times p$$
其中 $$A \times p_j^{m-1} = i$$
所以 $$\varphi(A) \times \varphi(p_j^{m-1}) = \varphi(i)$$
联立得 $$\varphi(i \times p_j) = \varphi(A) \times \varphi(p_j^{m-1}) \times p = \varphi(i) \times p_j$$
得证。

通式法

先挖坑，之后再补。

代码

if(x==1)return 0;p[1]=1;
for(int i=2;in||s[j]>f[i])break;f[s[j]*i]=s[j];
	if(s[j]

#include 
using namespace std;const int N=1e7;int p[N],f[N],s[N],tp,n;
int work(int x){
    if(x==1)return 0;p[1]=1;  
    for(int i=2;in||s[j]>f[i])break;f[s[j]*i]=s[j];
	    if(s[j]>n;cout<