线性筛与区间逆元
线性筛
线性筛可以在\(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)\)
和上面的代码大同小异。
区间逆元
设 \(p=k\cdot i + r\)
则 \(k=\lfloor \frac{p}{i} \rfloor\),\(r = p \% i\)。
又有有\(k\cdot i + r \equiv 0 \mod p\)
同乘\(i^{-1}\),\(r^{-1}\)可得:
\(k \cdot r^{-1} + i^{-1} \equiv 0 \mod p\)
即:\(i^{-1} \equiv -k\cdot r^{-1} \mod p\)
\(i^{-1} \equiv - \lfloor \frac{p}{i} \rfloor \cdot (p\%i)^{-1}\)
通过这个式子就可以区间求逆元了。