线性筛与区间逆元

线性筛

线性筛可以在\(O(n)\)的时间复杂度内，处理\([1,n]\)范围内的某种函数值，其中最经典的就是筛质数。

处理质数

线性筛的思想就是要保证，我们每一个数只被其最小的质因子筛掉，这样就可以保证时间复杂度。具体的我们枚举每一个\(i\)和小于等于\(i\)的所有质数\(pr[j]\)，然后筛掉\(i \times pr[j]\)，并且在遇到\(i | pr[j]\)时退出循环，因为\(pr[j]\)是从小到大枚举的，所以我们可以保证每一个数只被其最小的质因子筛掉。代码如下

点击查看代码

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e7;

int n;
bool vis[maxn+5];
int pr[maxn+5],prt;

signed main()
{
	scanf("%d",&n);
	for(int i=2;i<=n;i++)
	{
		if(!vis[i]) pr[prt++]=i;
		for(int j=0;j<prt;j++)
		{
			vis[i*pr[j]]=1;
			if(i%pr[j]==0) break;
		}
	}

	for(int i=0;i<prt;i++)
		printf("%d ",pr[i]);

	return 0;
}

处理欧拉函数

众所周知，欧拉函数有如下计算公式

\(\varphi(x)=x \cdot \prod (1-\frac{1}{p_i})\)

其中\(p\)为\(x\)的质因子。我们尝试使用线性筛求欧拉函数，令\(k=pr[j]\)。

如果\(i|k\)，则\(k\)是\(i\)的质因子，此时，\(\varphi(i \cdot k) = \varphi(i) \cdot k\)
否则，\(i\)与\(k\)互质，此时\(\varphi(i \cdot k) = \varphi(i) \cdot (k-1)\)

代码显然，不再赘述。

点击查看代码

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6;

int l,r;

int phi[maxn+5];
int pr[maxn+5],prt;
bool vis[maxn+5];

signed main()
{
	scanf("%d%d",&l,&r);

	for(int i=2;i<=maxn;i++)
	{
		if(!vis[i]) pr[prt++]=i,phi[i]=i-1;
		for(int j=0;j<prt&&i*pr[j]<=maxn;j++)
		{
			vis[i*pr[j]]=1;
			if(i%pr[j]==0)
			{
				phi[i*pr[j]]=phi[i]*pr[j];
				break;
			}
			phi[i*pr[j]]=phi[i]*phi[pr[j]];
		}
	}

	for(int i=l;i<=r;i++)
		printf("%d\n",phi[i]);

	return 0;
}

处理\(i^k\)（\(k\)为定值）

可以说是非常经典了。

若\(c=a\cdot b\)则\(c^k=a^k\cdot b^k\)。

又小于\(n\)的质数个数大概有\(\frac{n}{\log n}\)个，所以我们对于质数直接快速幂处理，再用线性筛筛合数即可，时间复杂度可视为线性。

处理约数个数

根据约数个数定理如果\(x=\prod p_i^{a_i}\)，那么有\(f(x)=\prod(1+a_i)\)。我们用\(g(x)\)表示\(x\)的最小质因数的指数加一。

如果\(x\)为质数那么\(f(x)=g(x)=2\)
否则令\(i=x\)，\(k=pr[j]\)
- 如果\(i|k\)，则\(k\)是\(i\)的最小质因子，此时\(f(i\cdot k)=\frac{f(i)\cdot (g(i)+1)}{g(i)}\)，\(g(i\cdot k)=g(i)+1\)
- 否则\(i\)与\(k\)互质，\(k\)小于\(i\)的最小质因子，此时\(g(i\cdot k)=2\)，\(f(i \cdot k)=2f(i)\)