更新日志
2024/12/04：添加线性筛法求欧拉函数完整证明以及模板
前言
一些话以及借鉴感谢[点击展开]
从这里开始重写（学）数论，从头开始，就不搬运原博客了。
欧拉函数部分借鉴这一篇博客，线性筛算法证明借鉴这一篇博客，在此一并感谢。
线性筛法模板改自原博客，感觉当初的证明很神秘，使用了容斥原理，也可以参考，这里就不写了，意义不大。
欧拉函数
概念
符号为 \(\varphi\)，英文 \(\rm phi\)。
\(\varphi(n)\) 表示所有小于等于 \(n\) 的数中，与 \(n\) 互质的数的个数。例如，\(\varphi(1)=1,\varphi(2)=1,\varphi(3)=2\dots\)
欧拉函数是积性函数，\(\forall(a,b)\in\{(a,b)|\gcd(a,b)=1\},\varphi(a\cdot b)=\varphi(a)\cdot\varphi(b)\)
基本公式与结论
结论一
\(\forall p\in \{素数\},\varphi(p)=p-1\)，这是显然的，任意小于 \(p\) 的数均与其互质，因为 \(p\) 是质数。
结论二
\(\forall i\in N^*\)，设其所有质因数为 \(p_1,p_2,\dots,p_s\)，则
\[\varphi(i)=i\cdot\prod_{j=1}^{s}\frac{p_j-1}{p_j} \]这就不是很显然了，所以我们推导一下：
引理1：若 \(p\) 为质数，\(k\) 为正整数，则 \(\varphi(p^k)=p^k-p^{k-1}\)
证明不难，考虑不与 \(p^k\) 互质且小于等于 \(p^k\) 的数 \(n\)，那么必然满足 \(p|n\)，那么在 \([1,p^k]\) 范围内，这样的 \(n\) 有 \(\frac{p^k}{p}=p^{k-1}\) 个。
因此，\(\varphi(p^k)=p^k-p^{k-1}\)。
引理2：根据唯一分解定理将 \(n\) 分解为 \(\prod\limits_{i=1}^{s}p_i^{k_i}\)，则 \(\varphi(n)=n\cdot\prod\limits_{i=1}^{s}\frac{p_i-1}{p_i}\)。
我们只需要推导一下公式即可：
\[\begin{aligned} \varphi(i) &=\varphi(\prod_{i=1}^s p_i^{k_i}) \\ &= \prod_{i=1}^s \varphi(p_i^{k_i}) \\ &= \prod_{i=1}^s (p_i^{k_i}-p_i^{k_i-1}) \\ &= \prod_{i=1}^s p_i^{k_i}\cdot\prod_{i=1}^s (1-\frac{1}{p_i}) \\ &= n\cdot \prod_{i=1}^s\frac{p_i-1}{p_i} \end{aligned} \]根据引理2，我们可以做到 \(O(\sqrt n)\) 求 \(\varphi(n)\)。
基础版模板
int solve(int n){
ll res=n;
for(int i=2;i<=n/i;i++){
if(n%i)continue;
res/=i;res*=i-1;
while(n%i==0)n/=i;
}
if(n>1)res/=n,res*=n-1;
return res;
}
线性筛求欧拉函数
理论
这是最常见的一种欧拉函数求法。
首先我们可以得到：
\[\varphi(n\cdot p)=\begin{cases}\varphi(n)\cdot(p-1) &\mathrm{if}\gcd(n,p)=1 \\ \varphi(n)\cdot p &\mathrm{if} \gcd(n,q)\ne 1\end{cases} \]上一种很简单，\(\varphi(p)=p-1\)。
至于下一种，不难发现 \(p|n\)，那么 \(p\) 为 \(n\) 的一个质因数，因此 \(n p\) 与 \(n\) 的质因数种类并无差别，根据引理2，整个公式后面的部分都是不变的，只是最前面的 \(n\) 变成了 \(n p\)，所以 \(\varphi(n p)=\varphi(n)\cdot p\)。
最后，因为线性筛的原理是用每个数的最小质因数筛掉它，所以就可以使每一个数的 \(\varphi\) 都只被计算一次。
证毕。
线性筛法模板
为了好看简洁，使用宏定义，更通用版本在第二个代码块内。
int cnt;
int prime[N];
bool st[N];
int phi[N];
void euler(int n){
phi[1]=1;
#define p prime[j]
rep(i,2,n){
if(!st[i]){
prime[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;p<=n/i;j++){
st[i*p]=true;
if(i%p==0){
phi[i*p]=phi[i]*p;
break;
}else phi[i*p]=phi[i]*(p-1);
}
}
}
无宏定义版本：
int cnt;
int prime[N];
bool st[N];
int phi[N];
void euler(int n){
phi[1]=1;
rep(i,2,n){
if(!st[i]){
prime[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;prime[j]<=n/i;j++){
st[i*prime[j]]=true;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}