求解 \(s(n)=\sum_{i=1}^nf(i)\)
\(min25\) 筛的想法就是分为质数的贡献，和所有的贡献来计算。
我们首先构造一个函数 \(F\) ，它满足以下条件
-
在质数处取值与 \(f\) 相等
-
是一个完全积性函数
-
能够快速求解前缀和
我们设 \(G(n,i)\) 表示 \(2-n\) 这些数中，所有的质数或者最小质因子大于 \(p_i\) 的数的 \(F\) 之和。
从 \(G(n,0)\) 开始递推，容易发现\(G(n,0)=\sum_{i=1}^nF(i)\) ，每次转移都是筛去一部分合数。由于 \(G(\left\lfloor \frac{n}{p_i}\right\rfloor ,i-1)\) 中还储存了 \(p_1-p_{i-1}\) 这些数的贡献，而这一部分数与 \(p_i\) 的乘积的最小质因子就不等于 \(p_i\) 的，也就是不应该被筛掉，所以还要额外加上这些数的贡献。故转移方程如下
令 \(p_{Limit}\) 是满足小于等于 \(\sqrt n\) 的最大的一个质数，则不会存在小于等于 \(n\) ，且满足最小质因子大于 \(p_{Limit}\) 的合数。故此时储存的就是所有质数的 \(F\) 之和。
考虑完质数的，我们在来考虑所有的。
令 \(S(n,i)\) 表示 \(2-n\) 这些数中，最小质因子大于 \(p_i\) 的数的 \(f\) 之和。那么也就是所有满足条件的质数的贡献加上满足条件的合数的贡献，我们直接枚举 \(p_k^e\) ，将所有存在 \(p_k^e\) 这一因子，且不存在 \(p_k^{e+1}\) 这一因子的合数的 \(f\) 加上。当 \(e\neq 1\) 时，\(p_k^e\) 也是一个合数，它的贡献也需要加上。所以 \(S\) 的转移方程如下
由于我们在求解过程中一直没有算上 \(1\) 的贡献，在最后加上就好了。
点击查看代码
inline void Init(int n) {
m=sqrt(n)+1; cnt=0;
for(LL i=1,j,x;i<=n;i=j+1) {
x=n/i; j=n/x; val[++cnt]=x;
if(x<=m) id1[x]=cnt;
else id2[j]=cnt;
c1[cnt]=x-1;
c2[cnt]=1LL*x*(x+1)/2LL-1;
}
for(int i=1,o;i<=idx;i++)
for(int j=1;j<=cnt && p[i]*p[i]<=val[j];j++) {
o=ID(val[j]/p[i]);
c1[j]-=1LL*(c1[o]-(i-1));
c2[j]-=1LL*p[i]*(c2[o]-sf[i-1]);
}
}
inline LL Get_phi(LL x,int y) {
if(p[y]>=x) return 0;
int o=ID(x);
LL g,res=(c2[o]-c1[o])-(sf[y]-y);
for(int k=y+1;k<=idx && 1LL*p[k]*p[k]<=x;k++) {
g=p[k];
for(int e=1;g<=x;e++, g*=p[k])
res+=(g/p[k])*(p[k]-1)*(Get_phi(x/g,k)+(e!=1));
}
return res;
}
inline LL Get_mu(LL x,int y) {
if(p[y]>=x) return 0;
int o=ID(x);
LL g,res=(0-c1[o])-(0-y);
for(int k=y+1;k<=idx && 1LL*p[k]*p[k]<=x;k++)
res-=Get_mu(x/p[k],k);
return res;
}
原文地址：http://www.cnblogs.com/oscaryangzj/p/16845815.html
