浅析狄利克雷卷积

定义

狄利克雷卷积是定义在数论函数间的一种二元运算:

\[(f\ast g)(n)=\sum_{xy=n}f(x)g(y) \]

也等价于下面这种形式:

\[(f\ast g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d}) \]

性质

  1. 若 \(f,h\) 是积性函数,则 \(f\ast g\) 也是积性函数

  2. 狄利克雷卷积满足交换律

    \[(f\ast g)(n)=\sum_{xy=n}f(x)g(y)=\sum_{xy=n}g(x)f(y)=(g\ast f)(n) \]

  3. 狄利克雷卷积满足对函数加法的分配律

    \[\begin{aligned} (f\ast(g+h))(n)&=\sum_{xy=n}f(x)(g+h)(y)\\ &=\sum_{xy=n}(f(x)g(y)+f(x)h(y))\\ &=\sum_{xy=n}f(x)g(y)+\sum_{xy=n}f(x)h(y)\\ &=(f\ast g)(n)+(f\ast h)(n) \end{aligned} \]

  4. 狄利克雷卷积满足结合律

    \[((f\ast g)\ast h)(n)=(f\ast(g\ast h))(n) \]

  5. 单位函数 \(\epsilon(n)=[n=1]\) 是狄利克雷卷积的单位元

    \[(\epsilon\ast f)(n)=\sum_{d\mid n}[d=1]f(\frac{n}{d})=f(n) \]

  6. 对于一个函数 \(f\) ,如果有另一个函数 \(g\) 满足 \(f\ast g=\epsilon\) ,则称 \(g\) 是 \(f\) 的逆元

  7. 积性函数的逆元也是积性函数

常见的数论函数

  • 单位函数 \(\epsilon (n)=[n=1]\)
  • 幂函数 \(\operatorname{id}_k(n)=n^k\) ,当 \(k=1\) 时为恒等函数 \(\operatorname{id}(n)=n\) ,当 \(k=0\) 时为常数函数 \(1(n)=1\)
  • 欧拉函数 \(\varphi(n)\)
  • 莫比乌斯函数 \(\mu(n)\)
  • 因数个数函数 \(d(n)=\sum_{d\mid n}1\)
  • 因数和函数 \(\sigma(n)=\sum_{d\mid n}d\)

常用结论

  1. \(\varphi\ast 1=\operatorname{id}\)

    \[(\varphi\ast 1)(n)=\sum_{d\mid n}\varphi(d) \]

    用归纳法:

    • \(n=1\) 时, \((\varphi\ast 1)(1)=\varphi(1)=1=\operatorname{id}(1)\)

    • \(n=2\) 时, \((\varphi\ast 1)(2)=\varphi(1)+\varphi(2)=2=\operatorname{id}(2)\)

    • 若 \(n\leq k\) 时, \((\varphi\ast 1)(n)=\operatorname{id}(n)\) 都成立

      那么 \(n=k+1\) 时

      • 若 \(n\) 为素数, \((\varphi\ast 1)(n)=\varphi(1)+\varphi(n)=n=\operatorname{id}(n)\)

      • 若 \(n\) 为合数,由于 \(\varphi\) 和 \(1\) 都为积性函数,所以 \(\varphi\ast 1\) 也是积性函数,设 \(n=n_2\times n_2\) 那么有:

        \[(\varphi\ast 1)(n)=(\varphi\ast 1)(n_1)\cdot(\varphi\ast 1)(n_2)=n_1n_2=n=\operatorname{id}(n) \]

    综上,命题得证

  2. \(\mu\ast 1=\epsilon\)

    \[(\mu\ast 1)(n)=\sum_{d\mid n}\mu(d) \]

    • \(n\not=1\)

      设 \(n=p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}\) , \(n\) 的约数 \(d=p_1^{q_1}p_2^{q_2}\cdots p_k^{q_k}\) ,由 \(\mu\) 的定义可知:对于任意 \(i\leq k\) ,只有 \(q_i=0\) 或 \(q_i=1\) 时才会对答案产生贡献,那么有 \(i\) 个 \(q\) 是 \(1\) 时,产生的贡献是 \((-1)^i\) ,所以原式等价于 \(\sum_{i=0}^k C_k^i(-1)^i=(1-1)^k=0\)

    • \(n=1\)

      \((\mu\ast 1)(1)=\mu(1)=1\)

    综上,\((\mu\ast 1)(n)=[n=1]=\epsilon(n)\)

  3. \(\mu\ast\operatorname{id}=\varphi\)

    \[(\mu\ast\operatorname{id})(n)=\sum_{d\mid n}\mu(d)\frac{n}{d} \]

    与第一个命题类似地,用归纳法:

    • \(n=1\) 时, \((\mu\ast\operatorname{id})(1)=\mu(1)=1=\varphi(1)\)

    • \(n=2\) 时, \((\mu\ast\operatorname{id})(2)=2\mu(1)+\mu(2)=1=\varphi(2)\)

    • 若 \(n\leq k\) 时, \((\mu\ast\operatorname{id})(n)=\varphi(n)\) 都成立

      那么 \(n=k+1\) 时

      • 若 \(n\) 为素数, \((\mu\ast\operatorname{id})(n)=n\mu(1)+\mu(n)=n-1=\varphi(n)\)

      • 若 \(n\) 为合数,由于 \(\mu\) 和 \(\operatorname{id}\) 都为积性函数,所以 \(\mu\ast\operatorname{id}\) 也是积性函数,设 \(n=n_2\times n_2\) 那么有:

        \[(\mu\ast\operatorname{id})(n)=(\mu\ast\operatorname{id})(n_1)\cdot(\mu\ast\operatorname{id})(n_2)=\varphi(n_1)\varphi(n_2)=\varphi(n) \]

    综上,命题得证

  4. \(1\ast1=d\)

    \[(1\ast 1)(n)=\sum_{d\mid n}1=d(n) \]

  5. \(\operatorname{id}\ast 1=\sigma\)

    \[(\operatorname{id}\ast 1)(n)=\sum_{d\mid n}d=\sigma(n) \]

  6. 莫比乌斯反演:\(f\ast1=g\Leftrightarrow f=g\ast\mu\)

    \[\sum_{d\mid n}f(d)=g(n)\Leftrightarrow f(n)=\sum_{d\mid n}g(d)\mu(\frac{n}{d}) \]

    可以用第二个结论和狄利克雷卷积的性质来证明:\(g\ast\mu=f\ast1\ast\mu=f\ast(1\ast\mu)=f\ast\epsilon=f\)

应用

例1

  • 题目:求 \(\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]\)

  • 分析:

    \[\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]\\ =&\sum_{i=1}^n\sum_{j=1}^m\epsilon(\gcd(i,j))\\ =&\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid \gcd(i,j)}\mu(d)\\ =&\sum_{d=1}^{\min(n,m)}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}1\\ =&\sum_{d=1}^{\min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor \end{aligned} \]

    这样就可以预处理出 \(\mu\) 的前缀和后求出分块处理

例2

  • 题目:求 \(\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)\)

  • 分析:

    \[\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)\\ =&\sum_{i=1}^n\sum_{j=1}^n\operatorname{id}(\gcd(i,j))\\ =&\sum_{i=1}^n\sum_{j=1}^n\sum_{d\mid \gcd(i,j)}\varphi(d)\\ =&\sum_{d=1}^{n}\varphi(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}1\\ =&\sum_{d=1}^{n}\mu(d)\lfloor\frac{n}{d}\rfloor^2 \end{aligned} \]

    同样地,预处理出 \(\varphi\) 的前缀和后求出分块处理即可

上一篇:Leetcode 121.买卖股票的最佳时机


下一篇:Day8 while和do while