当前位置 博文首页 > Wtothey_的博客:狄利克雷卷积+莫比乌斯反演+杜教筛

    Wtothey_的博客:狄利克雷卷积+莫比乌斯反演+杜教筛

    作者:[db:作者] 时间:2021-09-21 15:10

    狄利克雷卷积

    f*g(n)=\sum_{d\mid n}f(d)g(\frac{n}{d})


    狄利克雷卷积与数论函数构成,四个性质:

    • 封闭性
    • 结合律
    • 逆元
    • 幺元

    特殊卷积

    \mu *1(n)=\sum_{d\mid n}\mu(d) = \epsilon (n)互为逆元

    \varphi *1(n)=Id(n)

    Id*\mu(n)=\varphi(n)

    d(n)=1*1(n)


    莫比乌斯反演

    欧拉函数+莫比乌斯函数点这里

    约数反演

    定义:

    F(n)=\sum_{d\mid n} f(d) = f*1(n)

    反演:

    f(n)=\mu*F(n)=\sum_{d\mid n}F(d)\mu(\frac{n}{d})

    证明:(狄利克雷卷积)

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? F(n)=f*1(n)\Rightarrow F*\mu(n)= f (n)

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? f(n)=F*\mu(n)=\sum_{d\mid n} F(d)\mu(\frac{n}{d})

    倍数反演

    定义:

    F(n)=\sum_{n\mid d} f(d) = \sum_{i=1}f(in)\; \;\;\;\;\;\;\;\;\;(d=in)

    反演:

    f(n)=\sum_{ n \mid d} \mu(\frac{d}{n})F(d)

    证明:

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?\sum_{n\mid d}\mu(\frac{d}{n})F(d) =\sum_{i=1}\mu(i)F(in)\;\;\;\;\;\;\;\;\;d=in

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??=\sum_{i=1} \mu(i) \sum_{j=1}f(ijn)

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??=\sum_{m=1}f(mn)\sum_{i\mid m} \mu(i) \;\;\;\;\;\;\;\;\sum_{d\mid n}\mu(d)=\epsilon (n)

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??=\sum_{m=1}f(mn)\epsilon (m)\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;m=1

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? =f(n)


    数论分块

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? res = \sum_{i=1}^{n} \left \lfloor \frac {n}{i} \right \rfloor

    性质:

    1. 最多2\sqrt{n}块,O(\sqrt{n})
    2. 每一块最后一个i值为\left \lfloor \frac{n}{\left \lfloor \frac{n}{i} \right \rfloor}\right \rfloor
    ll aliquot_patition(int n){
        ll ans = 0;
        for(int l = 1, r = 0; l <= n; l = r + 1) {
            r = n / (n / l);  			// 求区间的右端,这是一个数学规律 
            ans += 1ll * (r - l + 1) * (n / l);    //个数*数值
        }
        return ans;
    }
    

    杜教筛

    低于线性时间复杂度上求解积性函数的前缀和(n很大的时候)

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? \sum_{i=1}^{n}f(i)

    基本套路:

    ? ? ? ? ? ? ? ? ? ? ? ?构造积性函数h和g,h = f * g,

    ? ? ? ? ? ? ? ? ? ? ? ?记? ? ???S(n)= \sum_{i=1}^{n}f(i),? 接下来求? ? ? ? ?\sum_{i=1}^{n}h(i)

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??\sum_{i=1}^{n}h(i)=\sum_{i=1}^{n}\sum_{d\mid i}g(d)f(\frac{i}{d})

    ? ? ? ? ? ? ?先枚举d,则i' = i*d(乘)? ? ? ? ? ?=\sum_{d=1}^{n}g(d) \sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}f(i)

    ? ? ? ? ? ? ?代换S? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???=\sum_{d=1}^{n}g(d)S\left \lfloor \frac{n}{d} \right \rfloor

    ? ? ? ? ? ? ?提出g(1)? ? ? ? ? ? ? ??g(1)S(n) =\sum_{i=1}^{n}h(i)-\sum_{d=2}^{n}g(d)S\left \lfloor \frac{n}{d} \right \rfloor? ? ? ? ? ? ??

    对后面的式子乘除分块后,时间复杂度O(n^2/3)

    应用

    一、S(n)= \sum_{i=1}^{n} \mu(i)

    ? ? ? ? ? ? 设\mu*1(n)=\epsilon(n),即h = \epsilon,g(1) = 1

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? g(1)S(n)=\sum_{i=1}^{n}\epsilon(i) - \sum_{d=2}^{n}1\cdot S(\left \lfloor \frac {n}{d} \right \rfloor)

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? =1-\sum_{d=2}^{n}S(\left \lfloor \frac{n}{d} \right \rfloor)? ? ? ? ?

    二、S(n)=\sum_{i=1}^{n}\varphi(i)

    ? ? ? ? ? ?设\varphi*1(n)=Id(n),即 h(i) = Id(i),g(1) = 1

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?g(1)S(n)=\sum_{i=1}^{n}i-\sum_{d=2}^{n}1\cdot S(\left \lfloor \frac{n}{d} \right \rfloor)
    ? ? ? ? ? ? ? ? ? ? ? ? ? ?

    三、S(n)=\sum_{i=1}^{n}i\cdot \varphi(i)

    ? ? ? ? ? ? ? ? ? ? ?先考虑狄利克雷卷积形式:

    ? ? ? ? ? ? ? ? ? ? 配g(n) = Id(n)?? ? ? ? ? ??\sum_{d\mid n}(d\cdot \varphi(i))g(\frac{n}{d})\\=\sum_{d\mid n} n \cdot \varphi(i)=n\cdot (\varphi * 1(i))=n\cdot Id(n)=n^{2}? ? ? ? ???

    ? ? ? ? ? ? ? ? ? ? 则? ? ? ? ? ? ? ? ? ? ? ??g(1)S(n)=\sum_{i=1}^{n}i^{2}-\sum_{d=2}^{n}i \cdot S(\left \lfloor \frac {n}{d} \right \rfloor)? ? ? ? ? ? ??

    ? ? ? ? ? ? ? ? ? ? 由此第一项可以由平方和公式?O(1)算出,后面分块。

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1^{2}+...+n^{2}=\frac{n(n+1)(2n+1)}{6}


    杜教筛取自:https://www.cnblogs.com/peng-ym/p/9446555.html

    ?

    cs