数论函数&莫比乌斯反演

· · 个人记录

真 莫比乌斯反演

突然发现之前学的（见下面）是假的（是对的，但是很麻烦）。于是又学了学简单一些的方法。

反演的主要依据：

ϵ = \mu * 1

然后直接将式子中的 ϵ 替换掉。

例：(n<m)（以下未经特殊说明，除法均为下取整）

\sum_{i = 1}^n\sum_{j=1}^m[gcd(i,j)=1] \sum_{i=1}^n\sum_{j=1}^mϵ(gcd(i,j)) \sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)}\mu(d) \sum_{i=1}^n\sum_{j=1}^m\sum_{d|i~and~d | j}\mu(d) \sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^n\mu(d) * [d|i] * [d|j] \sum_{d=1}^n\mu(d) * (\sum_{i=1}^n[d|i]) * (\sum_{j=1}^m[d|j]) \sum_{d=1}^n\mu(d) * \frac{n}{d} * \frac{m}{d}

一些小技巧

数论函数

详见洛谷日报：铃悬的数学小讲堂——狄利克雷卷积与莫比乌斯反演

数论函数的自变量为正整数。

运算率：

  1. 加法：逐项相加。

  2. 数乘：每项都与该数相乘。

  3. 狄利克雷卷积

狄利克雷卷积

若t = f × g, 则 t(n) = sigma(i|n){f[i] * g[n/i]}。

狄利克雷卷积具有：交换律，结合律，分配律。

单位元ε(x) = [x = 1]。单位元和任何数论函数做狄利克雷卷积，都得该数论函数本身。

求逆元：设g为f的逆元，即g * f = ε：

积性函数

仍然引用qy学长的课件：

在数论中的积性函数：
对于正整数n的一个算术函数 f(n)，若f(1)=1，且当a,b互质时f(ab)=f(a)f(b)，在数论上就称它为积性函数。
若对于某积性函数 f(n) ，就算a, b不互质，也有f(ab)=f(a)f(b)，则称它为完全积性的。

一些积性函数：

ϵ(n)=[n=1] id(n)=n id^k(n)=n^k \phi \mu

特别地，定义:

1(n)=id^0(n)=1

（上面的前面的1应该加粗）

需要记一些结论：

两个积性函数的狄利克雷卷积是积性函数

积性函数的逆是积性函数

应用：线性筛

φ(p^k)=(p−1)*p^k−1

同时，我们有一个重要结论：

id = φ×1

莫比乌斯反演

定义莫比乌斯函数

\mu

为1的逆元，若 g = f 1，则 f = g μ

如果

g[n] = sigma(i | n){f[i]}

则

f[n] = sigma(i | n){g[i] × μ[n / i]}

这就是莫反了。

需要记几个式子，莫比乌斯反演做不出来时可以用它们来搞（其实和莫比乌斯反演差不多）

(1用I来代替）

ε = I * \mu id = \phi * I \phi = id * \mu

其中 \epsilon = I * \mu 就硬背吧，反正经常用，不容易忘记。常用形式：[n=1] = \sum_{d|n} \mu(d)

然后是 id = \phi * I 的简单证明：

我们要证的是：n=\sum_{d|n}\phi(d)

我们把1~n 变成 \frac{1}{n} 到 \frac{n}{n}，总个数仍然为n。然后化简成最简分数，然后按照分母分类，会发现分母 d 只能是 n 的约数，并且个数为 \phi(d)（不互质会继续化简）。这样，这些数的总和就是n=\sum_{d|n}\phi(d)

求μ

易得，μ是积性的。

\mu(p^k) = 1(k = 0) \mu(p^k) = -1(k = 1) \mu(p^k) = 0(k > 1)

因此：

\mu(n) = (-1)^t(n = p_1 * p_2 * ... * p_t) \mu(n) = 0(n = p^k * a, k > 1)

Code:

//线性筛
for (register int i = 2; i <= limi; ++i) {
    if (!depri[i])  pri[++tot] = i, mu[i] = -1;
    for (register int j = 1; j <= tot && i * pri[j] <= limi; ++j) {
        depri[i * pri[j]] = true;
        if (i % pri[j] == 0)    { mu[i * pri[j]] = 0; break; }
        mu[i * pri[j]] = -1 * mu[i];
    }
}
//分解质因数
inline ll get_mu(ll num) {
    int type = 1;
    for (register ll i = 2; i * i <= num; ++i) {
        if (num % i == 0) {
            int ct = 0;
            while (num % i == 0)    ct++, num /= i;
            if (ct > 1) return 0;
            type *= -1;
        }
    }
    if (num > 1)    type *= -1;
    return type;
}

例题

数学公式好难打

建议看这篇博客：莫比乌斯反演-让我们从基础开始（主要看模型）和这篇博客：题解 P2257 【YY的GCD】（主要看套路）

f(d) 为 gcd(i,j)=d 的(i, j)的对数，F(n) 为gcd(i,j)= n和n的倍数 的对数。

这样，就有

F(n) = sigma(n|d) {f(d)} = (N/n) * (M/n) f(n)=sigma(n|d){F(d) * \mu(d/n)}

然后进行一系列推导，使得式子里(N/n) * (M/n)可以用分块做，μ的部分可以预处理出前缀和，然后对于这种题就差不多了。

这个要相对简单很多。

仍然设f(d) 为 gcd(i,j)=d 的(i, j)的对数，F(n) 为gcd(i,j)= n和n的倍数 的对数。

仍然有

F(n) = sigma(n|d) {f(d)} = (N/n) * (M/n) f(n)=sigma(n|d){F(d) * \mu(d/n)}

题目要求的正是f[k]。

莫反开始：

f(k) = sigma(k|d){F(d)\mu(d/k)} f(k) = sigma(k|d){\mu(d/k)(a/d)(b/d)}

令d = tk，即t = (d / k)；

f(k) = sigma(t){\mu(t)(a/tk)(b/tk)}

令A=a/k，B=b/k。

f(k) = sigma(t){\mu(t)(A/t)(B/t)}

其中μ可以预处理，A/t，B/t可以除法分块。

附：经打表检测，（除法为下取整）a/(b*c) = (a/b)/c = (a/c)/b

求：有多少种选择a1,a2,...,an的方案（ai <= m,an+1 = m)，存在整数k1,k2,...,kn,kn+1,使得

\sum_{i=1}^{n + 1}{a_i*k_i=1}

公式推导：

ans = \sum_{a_1=1}^m\sum_{a_2=1}^m...\sum_{a_n=1}^{m}{[gcd(a[i])\bot m]} = \sum_{a_1=1}^m\sum_{a_2=1}^m...\sum_{a_n=1}^{m}{[gcd(gcd(a[i]),m)=1]} =\sum_{a_1=1}^{m}\dots\sum_{a_n=1}^{m}\ \sum_{d|a_1,\dots d|a_n,\ d|m}\mu(d) =\sum_{d|m}\mu(d)*\sum_{a_1=1}^{\frac m d}\dots\sum_{a_n=1}^{\frac m d}1 =\sum_{d|m}\mu(d)*(\frac m d)^{n}