欧拉函数 \(φ(i)\)
欧拉函数是 \(1\sim n\) 的数中与 \(n\) 互质的个数，常写成 phi。
如何筛：
void init(){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]){phi[i]=i-1;prime[++cnt]=i;}
for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
对于 \(i\times prime\)?? 中只出现过一次最小质因子 \(prime\)?? 的情况（\(i\)?? 与 \(prime\)?? 互质），显然对于 \(1\sim i\)?? 中每一个与 \(i\)?? 的数乘上 \(prime\)?? ，都可以产生一个与 \(i\times prime\)?? 互质的数；对于 \(i\times prime\)?? 出现过两次及以上个 \(prime\)?? 的情况，就是要除掉 \(prime\)?? 与 \(i\times prime\)?? 这种情况（所以是 \(prime-1\)??）。
莫比乌斯函数 \(\mu(i)\)
我太菜了，不知道这个函数的性质除了颓式子还有什么用。
如何筛：
void get_mu(int n)
{
mu[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i]){prim[++cnt]=i;mu[i]=-1;}
for(int j=1;j<=cnt&&prim[j]*i<=n;j++)
{
vis[prim[j]*i]=1;
if(i%prim[j]==0)break;
else mu[i*prim[j]]=-mu[i];
}
}
}
就这样筛吧，就是根据百度百科上的性质来筛。
约数数和函数 \(\sigma(i)\)
字面意思，常写成 sigma （其实符号就是小写的 sigma）
如何筛：（远古的代码，有点沙比）
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,s[N],e[N],tot,p[N],v[N];
//tot：质数个数，p[i]：第i个质数，v[i]：i是否是质数
//s[i]：i的约数和，e[i]：不能被i的最小质因子整除的约数和
int main() {
cin>>n;
for(int i=2; i<=n; i++) {
if(!v[i]) {//当i是质数时
p[++tot]=i;//把i存进p
s[tot]=1+i;//i的约数和等于1+自身
e[tot]=1;//不能被i的最小质因子(即i)整除的约数和等于1
}
for(int j=1; j<=tot&&i*p[j]<=n; j++) {//详解见下文
v[i*p[j]]=1;
if(i%p[j]) {//如果i和p[j]互质
s[i*p[j]]=s[i]*(p[j]+1);
//↑s[i*p[j]]=s[i]*s[j];这种写法应该也可以
e[i*p[j]]=s[i];
} else {
s[i*p[j]]=s[i]*p[j]+e[i];
e[i*p[j]]=e[i];
break;
}
}
}
int ans=0;
for(int i=1; i<=n; i++) {//统计答案
ans+=s[i];
}
cout<<ans;
return 0;
}
约数个数和函数
字面意思，然而我也不知道符号表示是什么。
如何筛：
void init(){
f[1]=g[1]=1;
for(int i=2;i<=M;++i){
if(!vis[i]) pr[++pn]=i,f[i]=2,g[i]=1;
for(int j=1;j<=pn&&i*pr[j]<=M;++j){
vis[i*pr[j]]=1;
if(i%pr[j]==0){
g[i*pr[j]]=g[i]+1;
f[i*pr[j]]=f[i]/(g[i]+1)*(g[i*pr[j]]+1);
break;
}
else g[i*pr[j]]=1,f[i*pr[j]]=f[i]<<1;
}
}
}
我们对于一个数有唯一分解定理：\(p=p_1^{k_1}\times p_2^{k_2} ? \times p_n^{k_n}\)
所以对于一个数的约数个数为：\(\prod (k_i+1)\)? 表示每个分解出来的 \(p_i\) 选几个，因为可以不选，所以 \(+1\)。
我们定义 \(f(i)\)? 为 \(i\) 的约数个数和，\(g(i)\) 为 \(i\) 的最小质因子出现的次数（分解出来的对应的指数 \(k\)）。
当然，可以证得 \(f(i)\) 是积性函数。
根据线性筛的流程，当 \(i\)? 与 \(prime\)? 互质时，\(g(i\times prime)=1\)?，因为新 \(i\times prime\) 中 \(prime\) 的指数为 \(1\)，所以约数个数要在 \(f(i)\) 的基础上乘上 \(g(prime)+1=2=f(prime)\)，也印证了 \(f(i)\) 是积性函数？\(f(i\times prime)=f(i)\times 2=f(i)\times f(prime)\)；
反之，\(g(i\times prime)=g(i)+1\)，\(f(i\times prime)=[g(i\times prime)+1]\times \frac{f(i)}{g(i)+1}\)?，意思是先把 \(f(i)\) 中的关于 \(prime\) 的贡献项除掉，得出除掉 \(prime\) 以外的其他质因子的贡献，再乘上新的 \(prime\) 的贡献。