有的时候怕忘记，写篇小博客记录一下。
线性筛素数
inline void init(int n)
{
for(int i=2;i<=n;i++)
{
if(!vis[i]) prime[++cnt]=i;
for(int j=1;j<=cnt && i*prime[j];j++)
{
vis[i*prime[j]]=1;
if(!(i%prime[j])) break;
}
}
return;
}
线性筛求欧拉函数
inline void init(int n)
{
memset(vis,0,sizeof(vis));
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i]) {prime[++cnt]=vis[i]=i，phi[i]=i-1;}
for(int j=1;j<=cnt && i*prime[j]<=n;j++)
{
vis[i*prime[j]]=prime[j];
phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
}
}
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+phi[i];
return;
}
线性筛求莫比乌斯函数
inline void init(int n)
{
mu[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i]) {mu[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])) {mu[i*prime[j]]=0;break;}
else mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+mu[i];
return;
}
线性筛求约数个数
用 \(d_i\) 表示 \(i\) 的约数个数，\(num_i\) 表示 \(i\) 的最小质因子出现次数。
inline void init(int n)
{
d[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i])
{
prime[++cnt]=i;
d[i]=2,num[i]=1;
}
for(int j=1;j<=cnt && i*prime[j]<=n;j++)
{
vis[i*prime[j]]=1;
if(!(i%prime[j]))
{
num[i*prime[j]]=num[i]+1;
d[i*prime[j]]=d[i]/num[i*prime[j]]*(num[i*prime[j]]+1);
break;
}
else num[i*prime[j]]=1,d[i*prime[j]]=d[i]*2;
}
}
return;
}
线性筛求约数和
用 \(s_i\) 表示 \(i\) 的约数和，\(g_i\) 表示 \(i\) 的最小质因子的 \(p^0+p^1+p^2+\dots +p^k\).
inline void init(int n)
{
s[1]=g[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i]) vis[i]=1,prime[++cnt]=i,g[i]=i+1,s[i]=i+1;
for(int j=1;j<=cnt && i*prime[j]<=n;j++)
{
vis[i*prime[j]]=1;
if(!(i%prime[j]))
{
g[i*prime[j]]=g[i]*prime[j]+1;
s[i*prime[j]]=s[i]/g[i]*g[i*prime[j]];
break;
}
else
{
s[i*prime[j]]=s[i]*s[prime[j]];
g[i*prime[j]]=prime[j]+1;
}
}
}
return;
}