Min_25筛学习笔(口)记(糊)
说在前头
为了方便描述，以下全部用\(P\)指代质数集合，用\(p_i\)指代第\(i\)个质数，\(minp(i)\)指代\(i\)的最小质因子
作用
求一类积性函数\(f(x)\)的前缀和，这样的积性函数满足：
- 对于任意质数\(p\)，满足\(f(p)\)是一个低阶多项式
- \(f(p^k)\)，\(p\in P\)能快速计算答案
时间复杂度为\(O(\frac{n^{0.75}}{log n})\)
思路
大致分两步进行：
-
对所有的\(x=\lfloor \frac{n}{d}\rfloor\)筛出
\[\sum_{i=1}^{x}[i\in P]f(i) \] -
再借此求解原问题，对所有的\(x=\lfloor \frac{n}{d}\rfloor\)筛出
\[\sum_{i=1}^{n} f(i) \]
第一步
直接算\(f(i)\)可能十分难算，考虑到
于是我们先分别对所有的\(k\)求解\(\sum_{i=1}^{n}[i\in P]i^k\)，最后再合并起来
设
也就是\([1,n]\)中所有满足\(i\)是质数或者\(i\)的最小质因子大于\(p_j\)的\(i\)
考虑从\(G(n,j-1)\)转移到\(G(n,j)\)
这个转移过程中，我们会将\([1,n]\)范围内最小质因子是\(P_j\)的合数的贡献减去
如果\(P_j^2>n\)，那么\([1,n]\)范围内没有需要减去的贡献，故
否则，考虑需要减去的合数的贡献，假设其中任意一个合数\(=i*P_j(minp(i)\ge P_j)\)
那么需要减去的贡献是\(P_j^ki^k\)，于是
容斥一下，会发现
就是\(G(\lfloor \frac{n}{P_j}\rfloor,j)\)去掉第\(1-(j-1)\)个质数的贡献
综上，我们有：
初始值：
其中\(sum_i=\sum_{j=1}^{i}p_i^k\)，因为我们只需要\(\le \sqrt{n}\)的质数，所以可以直接筛出这些质数以及\(sum\)
那么我们所需要的答案就是\(G(n,tot)\),其中\(tot\)是质数的总数量
总结一下，我们所做的就是一个类似埃氏筛的过程
我们先假设所有的数都是质数，按质数的方式计算出\(G(n,0)\)，但是这其中所有合数的答案都是错误的
于是我们依次枚举所有质数，依次筛掉以当前质数作为最小质因子的合数的贡献，直到\(g\)中只剩下了质数。
这个方法妙就妙在：虽然\(f(p),p\in Prime\)是低阶多项式，容易求解，但想要筛出所要的质数却需要较高的复杂度，而\(\sum_{i=1}^{n} i^k\)就相对来说好求的多了，并且筛的过程中我们只需要\(\le \sqrt{n}\)的质数。
第二步
我们开始求答案了，同样考虑：
我们分开考虑质数的贡献与合数的贡献：
质数部分的贡献显然是：
注意这里面的\(g\)是将所有的\(i^k\)加了起来得到的结果。
再考虑合数部分的贡献，我们可以枚举这些合数的最小质因子\(p\)以及它的指数，然后利用\(f(x)\)是积性函数的性质转移即可：
例题
题目中的\(f(x)\)满足\(f(p^c)=p\oplus c,p\in P\)
于是有\(f(p)=p-1,p\in P,p \not= 2\)，\(f(2)=3\)需要特判
于是就可以按上面的套路来计算，先将所有的数当成质数来计算
我们可以将质数的贡献也拆分成质数和-质数个数（特判\(2\)），分别设为\(h\)和\(g\)
同时观察到无论怎样转移，当前计算的\(S(i,j)\)中的\(i\)一定是某一个\(\lfloor \frac nx \rfloor\)，而这样的数只有不超过\(2\sqrt{n}\)个，于是我们只需要维护它们的\(g\)与\(h\)
于是初值为\(g(n)=\frac{n(n+1)}{2},h(n)=n-1\)，然后依次筛即可
最后的\(S\),我们采用递归的方式，不需要记忆化，直接用之前的式子计算就行了
注意如果此时\(S(n,j)\)中\(j=1\)，那么需要额外加上\(f(2)\)少计算的2个贡献，
参考代码更好理解：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int mod=1e9+7;
typedef long long ll;
ll mx,p[N],pcnt;//h正在筛的质数个数，g正在筛的质数和
bool pd[N];
int sum[N],g[N],h[N];//sum是预处理的质数前缀和
inline int add(int x,int y){return (x+y>=mod)?x+y-mod:x+y;}
inline int dec(int x,int y){return (x-y<0)?x-y+mod:x-y;}
inline void init(){
for(int i=2;i<=mx;++i){
if(!pd[i]) p[++pcnt]=i,sum[pcnt]=add(sum[pcnt-1],i);
for(int j=1;j<=pcnt&&i*p[j]<=mx;++j){
int num=i*p[j];pd[num]=1;
if(i%p[j]==0) break;
}
}
}
ll n,w[N],id1[N],id2[N];//w是所有的n/i，tot是w的个数
int tot;
inline int S(ll x,int j){
if(x<=1||p[j]>x) return 0;
int k=(x<=mx)?id1[x]:id2[n/x];
int ret=dec(g[k],add(sum[j-1],h[k]-j+1));//质数的答案
if(j==1) ret=add(ret,2);//特殊考虑2
for(int i=j;i<=pcnt&&p[i]*p[i]<=x;++i){
ll p1=p[i],p2=p[i]*p[i];
for(int t=1;p2<=x;++t,p1=p2,p2*=p[i]){//枚举v最小质因子及其指数
ret=add(ret,(p[i]^t)*S(x/p1,i+1)%mod);
ret=add(ret,(p[i]^(t+1))%mod);
}
}
return ret;
}
int main(){
scanf("%lld",&n);
mx=ceil(sqrt(n+0.5));
init();
ll r;
for(ll l=1;l<=n;l=r+1){
r=n/(n/l);
w[++tot]=n/l;
h[tot]=(w[tot]-1)%mod;//去掉特殊的1
g[tot]=(w[tot]%mod)*((w[tot]+1)%mod)%mod;
if(g[tot]&1) g[tot]+=mod;
g[tot]=g[tot]/2-1;
if(w[tot]<=mx) id1[w[tot]]=tot;
else id2[r]=tot;
}//预处理
for(int j=1;j<=pcnt;++j){//依次筛质数
for(int i=1;i<=tot&&p[j]*p[j]<=w[i];++i){
ll x=w[i]/p[j];
int k=(x<=mx)?id1[x]:id2[n/x];
h[i]=dec(h[i],h[k]-j+1);
g[i]=dec(g[i],p[j]*dec(g[k],sum[j-1])%mod);
}
}//第一步
int ans=S(n,1);//第二步
printf("%d\n",add(ans,1));//最后将1的贡献加回来
return 0;
}