前置知识
算法简介
用于计算数论函数前缀和。
思想
设有一个数论函数 \(f\) ,要计算它的前缀和,即 \(S(n)=\sum \limits_{i=1}^n f_i\) 。
再找一个数论函数 \(g\) ,考虑它们狄利克雷卷积的前缀和:
\(\sum \limits_{i=1}^n (f*g)(i)=\sum \limits_{i=1}^n \sum \limits_{d|i}f(d)g(\frac{i}{d})=\sum \limits_{d=1}^n g(d) \sum \limits_{i=1}^{\lfloor \frac{n}{d} \rfloor} f(i)=\sum \limits_{d=1}^n g(d)S(\lfloor \frac{n}{d} \rfloor)\) .
发现这个式子的第一项,即 \(g(1)S(n)\) ,就是我们要求的 \(S(n)\) 。
用前缀和的思想, \(g(1)S(n)=\sum \limits_{i=1}^n g(i)S(\lfloor \frac{n}{i} \rfloor)-\sum \limits_{i=2}^n g(i)S(\lfloor \frac{n}{i} \rfloor)\) 。
因为 \(g(1)S(n)\) 就是我们要求解的东西,所以把前一部分换成 \(\sum \limits_{i=1}^n (f*g)(i)\) ,得到 \(g(1)S(n)=\sum \limits_{i=1}^n (f*g)(i)-\sum \limits_{i=2}^n g(i)S(\lfloor \frac{n}{i} \rfloor)\) 。
这样,如果找的积性函数 \(g\) 有比较好的性质,能够快速算出 \(\sum \limits_{i=1}^n (f*g)(i)\) 和 \(g\) 的前缀和,就可以数论分块,同时递归处理 \(S(\lfloor \frac{n}{i} \rfloor)\) ,从而得到 \(S(n)\) 了。
直接写,复杂度是 \(O(n^{\frac{3}{4}})\) 。
但是,这个做法还可以优化。可以用线性筛先筛出前 \(O(n^{\frac{2}{3}})\) 个数,后面再用杜教筛。这样做,复杂度是 \(O(n^{\frac{2}{3}})\) 。
例子
1.求 \(\varphi\) 的前缀和。
有性质 \(\varphi*1=id\) ,同样把上面的 \(f\) 取为 \(\varphi\) , \(g\) 取为 \(1\) 即可。(\(id(n)=n\))
int PHI(int x)
{
if(x<N) return phi[x];//已经筛出来的部分
if(ans[x]) return ans[x];
int sum=(1+x)*x/2,l=0,r=1;
while(l<=x)
{
l=r+1;
if(x/l) r=MIN(x/(x/l),x);
else r=x;
sum-=(r-l+1)*PHI(x/l);
}
return ans[x]=sum;
}
2.求 \(\mu\) 的前缀和。
有性质 \(\mu*1=\varepsilon\) ,那么,把上面的 \(f\) 取为 \(\mu\) , \(g\) 取为 \(1\) 即可。(\(\varepsilon(n)=[n=1]\))
int MU(int x)
{
if(x<N) return mu[x];
if(ans[x]) return ans[x];
int sum=1,l=0,r=1;
while(l<=x)
{
l=r+1;
if(x/l) r=MIN(x/(x/l),x);
else r=x;
sum-=(r-l+1)*MU(x/l);
}
return ans[x]=sum;
}