可以用来筛出一个积性函数的前缀和。这个积性函数要满足当(x)是质数时，(f(x))可以快速求出，(f(x^k))也可以快速算出。
首先我们要处理出一个(g(x)=sum_{xin prime}f(x))，处理这个的主要思想和埃氏筛法差不多。我们只要(x)是质数时候的值，那么，我先假设所有的数是质数，然后一步步筛掉不是质数的(x)的函数值。
具体地，先把(sqrt{ n }) 以内的质数筛出来，我们设(g(n,j))表示已经筛掉了(n)以内的，含有小于等于(p_j)的质因子的和数的答案。考虑从(g(n,j-1))转移到(g(n,j))，也就是我们要把那些最小质因子是(p_j)的数的函数值从中剪掉。
如果(p_j^2>n)， 那么就没有这样的数，所以(g(n,j)=g(n,j-1))。所以(p_j)只要到枚举到(sqrt{n})，(g(sqrt{n},|P|))，就是最后的前缀和。
要不然就要减掉一些。因为这是积性函数,我们直接把质因子(p_j)提出来，乘上剩下的部分，也就是(f(p_j)*[g(frac{n}{p_j},j-1)-g(p_j-1,j-1)]),后面减去的部分就是那些最小质因子比(p_j)小的。显然(g(p_j-1,j-1)=sum_{xin prime}{f(x)})，我们在筛质数的时候预处理一下。所以(g(n,j)=g(n,j-1)-f(p_j)*[g(frac{n}{p_j},j-1)-sum_{xin prime}f(x)])。
至于怎样实现，可以看看这个筛质数前缀和的代码。
#define id(x) ( (x)<=max_d?id1[x]:id2[d/(x)] )
__int128 cal(ll d)
{
cnt=0;
ll last;
__int128 now;
for(ll i=1;i<=d;i=last+1)
{
now=d/i;last=d/now;
num[++cnt]=now;
f[cnt]=now*(now+1)/2-1;
if(now<=max_d)id1[now]=cnt;
else id2[d/now]=cnt;
}
For(j,1,p[0])
{
__int128 m=(__int128)p[j]*p[j];
if(m>d)break;
for(int i=1;i<=cnt&&num[i]>=m;i++)
{
int t=id(num[i]/p[j]);
f[i]-=(__int128)p[j]*(f[t]-sum[p[j]-1]);
}
}
return f[id(d)];
}
有一个很神奇的结论，就是(lfloor frac {n}{p_i*p_J} floor=lfloor frac{lfloor frac{n}{p_i} floor}{p_j} floor),所以我们只要把(n)的整除分块的那(2sqrt{n})个值全部处理出来就行了。
接下来，我们来计算一个积性函数的前缀和。设(S(n,j))表示(1)到(n)的前缀和，并且含有(>=p_j)的质因子的和。
那么有(S(n,j)=g(n,|P|)-sum_{i=1}^{j-1} f(p_i)+sum_{k>=j}sum_{e}^{p_k^e<=n}(F(p_k^e)*S(frac{n}{p_k^e},j+1)+F(p_k^{e+1})))。就是枚举最小质因子以及它的幂次，然后以后只能用(>p_k)的质因子。加上(F(p_k^{e+1}))是因为这一项枚举不到就要单独加上。