前置知识
算法简介
用于计算数论函数前缀和。
思想
设有一个数论函数 (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}
floor} f(i)=sum limits_{d=1}^n g(d)S(lfloor frac{n}{d}
floor)) .
发现这个式子的第一项,即 (g(1)S(n)) ,就是我们要求的 (S(n)) 。
用前缀和的思想, (g(1)S(n)=sum limits_{i=1}^n g(i)S(lfloor frac{n}{i}
floor)-sum limits_{i=2}^n g(i)S(lfloor frac{n}{i}
floor)) 。
因为 (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}
floor)) 。
这样,如果找的积性函数 (g) 有比较好的性质,能够快速算出 (sum limits_{i=1}^n (f*g)(i)) 和 (g) 的前缀和,就可以数论分块,同时递归处理 (S(lfloor frac{n}{i}
floor)) ,从而得到 (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;
}