利用线性筛法解决的数学函数或问题小汇(省选复习)

准备省选的过程中发现数学这一块的结论是学的快忘得也快,而因此就有了总结出一篇博客来深化记忆同时也方便

大家学习，我会在接着的几个博客中重点梳理数学相关的知识内容,有什么疏漏或不足之处还望指出。

①线性筛法求素数（略）

void init()
{for(int i=2;i<=n;i++){if(!vis[i])prime[++cnt]=i;for(int j=1;j<=cnt;j++){long long tmp=i*prime[j];if(tmp>=N)break;vis[tmp]=1;if(i%prime[j]==0)break;}}
}

②线性筛法求莫比乌斯函数：

基本方法是这样的: 

若x为素数 则mu[x]=-1

若x由prime[j]*i筛到且i%prime[j]!=0     则mu[x]=-mu[i]

若x由prime[j]*i筛到且i%prime[j]==0    则mu[x]=0

void init()
{for(int i=2;i<=n;i++){if(!vis[i])mu[i]=-1,prime[++cnt]=i;for(int j=1;j<=cnt;j++){long long tmp=i*prime[j];if(tmp>=N)break;vis[tmp]=1;if(i%prime[j]==0)break;mu[tmp]=-mu[i];}}
}

③线性筛法求欧拉函数:

若x为素数 则mu[x]=x-1

若x由prime[j]*i筛到且i%prime[j]!=0     则mu[x]=mu[i]*(prime[j]-1)

若x由prime[j]*i筛到且i%prime[j]==0    则mu[x]=mu[i]*prime[j]

void init()
{for(int i=2;i<=n;i++){if(!vis[i])phi[i]=i-1,prime[++cnt]=i;for(int j=1;j<=cnt;j++){long long tmp=i*prime[j];if(tmp>=N)break;vis[tmp]=1;if(i%prime[j]==0){phi[tmp]=phi[i]*j;break;}phi[tmp]=phi[i]*(j-1);}}
}





④线性筛法求约数和、约数个数(代码略)