积性函数
在数论题目中,经常需要根据一些积性函数的性质,求出一些式子的值。
积性函数:对于函数f(x)
,若gcd(a, b)=1
,则有f(ab)=f(a)f(b)
,则f(x)
为积性函数。
常见的积性函数:
d(x)=\sum_{d|x}1
表示约数个数函数
\sigma(x) = \sum_{d|x}d
表示约数和
\phi(x)=\sum_{i=1}^{x}[gcd(i, x)=1]
欧拉函数
\mu(x)
莫比乌斯函数
积性函数满足以下性质:
若f(x), g(x)
为积性函数,则以下h(x)
也为积性函数
h(x) = (f*g)(x)
两个积性函数的Dirichlet卷积也是积性函数
h(x) = f(x)g(x)
h(x) = f^p(x)
h(x) = f(x^p)
杜教筛
在莫比乌斯反演的题目中,当数据范围使得线筛不可取时,可以使用杜教筛来快速求得积性函数的前缀和。杜教筛的时间复杂度为O(n^{\frac{3}{4}})
。
对于数论函数f(x)
,若该函数为积性函数,欲求S(n) = \sum_{x=1}^{n}f(x)
,也就是积性函数前缀和。
我们再找一个数论函数g(x)
,使得很容易求得f*g
的前缀和,利用这个“很容易”来加速求得f
的前缀和。
先来推断以下式子:
那么有g(1)S(n) = \sum_{i=1}^{n}g(i)S(\frac{d}{n}) - \sum_{i=2}^{n}g(i)S(\frac{d}{n}) = \sum_{i=1}^{n}(f*g)(i) - \sum_{i=2}^{n}g(i)S(\frac{d}{n})
,这个是杜教筛的核心式子。如果可以找到一个合适的数论函数g
可以很快的求得\sum_{i=1}^{n}(f*g)(i)
,就可以用数论分块递归地求解。
伪代码如下:
int get_Sum_f (int n) {
int ans = (f*g)_sum(n); // f和g卷积后的前缀和
for (int l=2, r; l<=n; ) { // 从2开始
int value = n/l; //分块,value为该块的权值,区间为[l, r]
r = n/value;
ans -= get_Sum_f(value)*g_sum(l,r); //
l = r+1;
}
return ans;
}
例子
1.求欧拉函数\phi(x)
的前缀和。用I=1
来和欧拉函数卷积。\phi*I=id
,即\sum_{d|n}\phi(d)=n
。
下面我写的是先提前处理了一部分前缀和,可以更快的求和。
typedef long long ll;
ll GetPhi(ll n){
if (n < N) return phi[n];
if (mp1.count(n)) return mp1[n];
ll ans = n * (1+n) / 2, l, r;
for (l=2; l<=n; l=r+1){
r = n/(n/l);
ans -= (r-l+1) * GetPhi(n/l);
}
return mp1[n] = ans;
}
2.求莫比乌斯函数\mu(x)
的前缀和。仍选取函数I=1
来卷积。\mu*I=ε, ε(x) = [x=1]
。
ll GetMu(ll n) {
if (n < N) return mu[n];
if (mp2.count(n)) return mp2[n];
ll ans = 1, l, r;
for (l=2; l<=n; l=r+1) {
r = n/(n/l);
ans -= (r-l+1) * GetMu(n/l);
}
return mp2[n] = ans;
}
3.求\sum_{i=1}^{n}\phi(i)i
。先设出g(x), f(x) = \phi(x)x
,考虑卷积(f*g)(x) = \sum_{d|x}f(d)g(\frac{x}{d})=\sum_{d|x}\phi(d)*d*g(\frac{x}{d})
,注意到当g(x)=x
时可以很好的计算出上式,上式=\sum_{d|x}\phi(d)*d*\frac{x}{d}=x\sum_{d|x}\phi(d)=x^2
,x^2
的前缀和为\frac{n*(n+1)*(2n+1)}{6}
。
x^2
的前缀和为\frac{n*(n+1)*(2n+1)}{6}
x^3
的前缀和为(1+2+···+n)^2
0 条评论