很萌很可爱！就是把纸质笔记上 letex 写在这里有亿点慢
线性筛
埃氏筛， \(O(n\log\log n)\) ，思路是 ⌈ 标记所有质数的倍数 ⌋
这样每个合数可能会被标记好几次，我们改进一下，让每个合数只有一种被标记的方式，即 ⌈ 最小质因子 * 常数 ⌋
具体而言，⌈ 枚举 \(2\to x\) 把当前数 \(i\) 跟质数表每个不超过自己的最小质因子的质数成绩来标记掉 ⌋，这样就可以 \(O(n)\) 筛素数了！
int p[MN], top, phi[MN], vis[MN];
vis[1]=1, phi[1]=1;
for(int i=2; i<=n; ++i) {
if(!vis[i]) p[++top]=i, phi[i]=i-1;
for(int j=1; j<=top&&i*p[j]<=n; ++j) {
int x=i*p[j]; vis[x]=1;
if(i%p[j]!=0) phi[x]=(p[j]-1)*phi[i];
else { phi[x]=phi[i]*p[j]; break; }
}
}
欧拉函数
\(\phi(x)\) 表示 ⌈ 小于等于 \(x\) 的与 \(x\) 互质的数的个数 ⌋
这个 \(\phi(x)\) 怎么求呢，考虑 ⌈ 容斥 ⌋ 酱！
设 \(A_x\) 表示 \([1,n]\) 种是 \(x\) 的倍数的集合
\[\phi(n)=|\overline A_1\bigcap \overline A_2\bigcap \overline A_3...\bigcap \overline A_n| \]\[\phi(x)=n-\sum_{q=1}^{n} {(-1)^q\sum_{1\leq d_i\leq n,d_i<d_{i+1}}{|A_{d_1}\bigcap A_{d2}...\bigcap A_{d_q}|}} \]\[\phi (n)=n(1-\sum_{q=1}^{cntp}{\prod_{1\leq d_i\leq cntp,d_i<d_{i+1}}{p_{d_i}}}) \]\[\phi (n)=n\prod_{i=1}^{cntp} (1-\frac{1}{p_i})=n\prod_{i=1}^{cntp} \frac{p_i-1}{p_i} \]显然可以在 $O(\sqrt n) $ 时间求出质因子并且乘好，且显然不会有小数
int getPhi(int n){
int ans=n;
for(int i=2; i*i<=n; ++i)
if(n%i==0){
ans=ans*(i-1)/i;
while(n%i==0) n/=i;
}
if(n>1) ans=ans*(n-1)/n ;
return ans;
}
积性函数
定义正整数域上的函数 \(f(x)\)，对于 \(\gcd (x,y)=1\) 的 \(x,y\) 有 \(f(xy)=f(x)f(y)\) 则称 \(f(x)\) 为积性函数
欧拉函数就是一个积性函数，对于符合条件的 \(x,y\) 祂们没有相同的质因子所以 \(\phi(xy)=\phi(x)\phi(y)\) 这个式子可以帮我们线性递推！！递推的起点可以是对于质数 \(p\) 有 \(\phi(p)=p-1\)
int n, top, p[MN], phi[MN];
bool vis[MN];
memset(vis,1,sizeof(vis));
vis[1]=0, phi[1]=1;
for(int i=2; i<=INF; ++i) {
if(vis[i]) p[++top]=i, phi[i]=i-1;
for(int j=1; j<=top&&i*p[j]<=INF; ++j) {
int x=i*p[j]; vis[x]=0;
if(i%p[j]!=0) phi[x]=(p[j]-1)*phi[i];
else { phi[x]=phi[i]*p[j]; break; }
}
}
不仅仅是欧拉函数，乘性函数大都可以用线性筛递推，比如约数和，约数个数，递推的时候为了保证找到互质可以分类讨论，具体而言，⌈ 记录最小因子的最高次幂 ⌋ ⌈ 质数用特殊性质求 ⌋ ⌈ 质数的幂用特殊性质求 ⌋ 就可以了
欧拉函数常用性质
质数 \(p\) 的 \(\phi(p)=p-1\)
若 \(n=p^k\)，\(p\) 是质数，则 \(\phi(n)=(p-1)p^{k-1}\)
若 \(q\) 是质数，\(q\mid n\)，则 \(\phi(nq)=q\phi(n)\)
若 \(q\) 是质数，\(q\nmid n\)，则 \(\phi(nq)=(q-1)\phi(n)\)
对于 \(n\) 有 $ n=\sum_{d\mid n}{\phi(d)}$
标签：phi,函数,int,质数,MN,vis,线性,欧拉 From： https://www.cnblogs.com/chelsyqwq/p/17625755.html