——by sunzz3183
欧拉函数
出自：
定义
\[\varphi (n)=\sum\limits_{i=1}^{n} [\gcd(n,i)=1] \]筛法
原理
\[\varphi(n)=n\prod_{i=1}^{k}(1-\frac{1}{p_i}) \]所以：
- 当 \(n\) 为质数的时候 \(\varphi (n)=n-1\)
- 设 \(d=\frac{n}{p}\) 其中 \(p\)为 \(n\) 的最小质因子。
-
当 \(p\) 是 \(d\) 的某个质因子时，则 \(\varphi (n)=\varphi (d)\times p\)
-
当 \(p\) 与 \(d\) 互质时，\(\varphi (n)=\varphi (d)\times \varphi (p)\)
代码
int cnt,q,prime[M],phi[N],mu[N];
bool is_p[N];
void init(int n){
phi[1]=mu[1]=1;
for(int i=2;i<=n;i++){
if(!is_p[i])prime[++cnt]=i,phi[i]=i-1,mu[i]=-1;
for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
is_p[i*prime[j]]=1;
if(!(i%prime[j])){
phi[i*prime[j]]=phi[i]*prime[j];
mu[i*prime[j]]=0;
break;
}
phi[i*prime[j]]=phi[i]*(prime[j]-1);
mu[i*prime[j]]=-mu[i];
}
}
}
重要公式：
\((1)\)
\[\sum\limits_{d|n} \varphi (d)=n \]证明：
设 \(f(n)=\sum\limits_{d|n} \varphi (d)\)
由筛法的原理1,2可知
\[\varphi (p^k)=\varphi (p)\times p^{k-1}=(p-1)\times p^{k-1}=p^k-p^{k-1} \]对于
\[\sum\limits_{d|p^k} \varphi (d) \]显然，\(d=\left \{ p^0,p^1,p^2,...,p^k\right \}\)。那么有
\[\begin{aligned} \\&=\sum\limits_{i=0}^k \varphi (p^i) \\&=(\sum\limits_{i=1}^k p^i-p^{i-1})+1 \\&=p^k-p^{k-1}+p^{k-1}-p^{k-2}+...+p-1+1 \\&=p^k \end{aligned}\]\(\therefore f(p^k)=p^k\)
\(\because f(ab)=\sum\limits_{d|ab} \varphi (d)=(\sum\limits_{d|a} \varphi (d)) \times (\sum\limits_{d|b} \varphi (d))=f(a)\times f(b)\)
\(\therefore f(n)\)为积性函数。
\[\begin{aligned} \\&\therefore f(n) \\&=f(p_1^{c_1}\times p_2^{c_2}\times p_3^{c_3}\times ...\times p_k^{c_k}) \\&=f(p_1^{c_1})\times f(p_2^{c_2})\times f(p_3^{c_3})\times ...\times f(p_k^{c_k}) \\&= p_1^{c_1}\times p_2^{c_2}\times p_3^{c_3}\times ...\times p_k^{c_k} \\&=n \end{aligned}\]\((2)\)
\[\begin{aligned} \\&\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} [\gcd(i,j)=1] \\&=\sum\limits_{i=1}^{n}(2\sum\limits_{j=1}^{i}[\gcd (i,j)=1])-1 \\&=2 \sum\limits_{i=1}^{n}\varphi (i)-1 \end{aligned}\]可以使用前缀和，使得 \(O(1)\) 查询。
\((2.5)\)
\[\begin{aligned} \\&\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \gcd(i,j) \\&= \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d|gcd(i,j)} \varphi (d) \\&= \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d|i,d|j} \varphi (d) \\&= \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d=1}^{n} \varphi (d)[d|i][d|j] \\&=\sum\limits_{d=1}^{n} \varphi (d) \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} [d|i][d|j] \\&=\sum\limits_{d=1}^{n} \varphi (d) \left \lfloor \frac{n}{d} \right \rfloor ^2 \end{aligned}\]\((3)\)
莫比乌斯反演（拓展）
\[\begin{aligned} \\&\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \gcd(i,j) \\&= \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d|gcd(i,j)} \mu (d) \\&=\sum\limits_{i=1}^{n} \sum\limits_{d=1}^{min(i,m)} \mu (d)\left \lfloor \frac{min(i,m)}{d} \right \rfloor \\&=\sum\limits_{d=1}^{min(n,m)} \mu (d)\left \lfloor \frac{n}{d} \right \rfloor \left \lfloor \frac{m}{d} \right \rfloor \end{aligned}\]扩展欧拉定理
\[a^b \equiv \begin{cases} a^{b\mod{\varphi(m)}}&a\perp m\\a^b&![a\perp m],b<\varphi (m)\\a^{b\mod{\varphi (m)} +\varphi (m)}&![a\perp m],b\geq\varphi (m)\end{cases}\mod{m} \]互质可以不要
\[a^b \equiv \begin{cases} a^{b\mod{\varphi(m)}}&b<\varphi (m)\\a^{b\mod{\varphi (m)} +\varphi (m)}&b\geq\varphi (m)\end{cases}\mod{m} \] 标签：begin,limits,定理,varphi,times,笔记,aligned,sum,欧拉 From： https://www.cnblogs.com/sunzz3183/p/17087498.html