积性函数

在数论题目中,经常需要根据一些积性函数的性质,求出一些式子的值。
积性函数:对于函数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^2x^2的前缀和为\frac{n*(n+1)*(2n+1)}{6}

x^2的前缀和为\frac{n*(n+1)*(2n+1)}{6}
x^3的前缀和为(1+2+···+n)^2


0 条评论

发表评论

邮箱地址不会被公开。