数论函数

· · 算法·理论

5. 数论函数

我们给出如下定义:

积性函数对乘法封闭:

常见的积性函数:

Möbius 函数的性质

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

:::::success[组合意义]

考察 n 的质因数分解 \prod\limits_{i=1}^k p_i^{c_i}。记 n'=\prod \limits_{i=1}^k p_i,显然 \sum \limits_{d \mid n} \mu(d)=\sum \limits_{d \mid n'} \mu(d)。

枚举恰好选择 i 种质因子,由二项式定理

\sum \limits_{d \mid n'} \mu(d)=\sum_{i=0}^k (-1)^i\binom{k}{i}=[k=0]

当且仅当 n=1 时 k=0,证毕。

:::::

对一个积性函数 f,若对质数 p 都可 O(1) 求解 f(p^k),则 f(1 ) \sim f(n) 可用线性筛在 O(n) 时间内预处理。具体地,我们给出如下算法流程:

5.1 欧拉函数

5.2.1 费马小定理 & 欧拉定理

欧拉定理 对于正整数 a,m,若 \gcd(a,m)=1,则

a^{\varphi(m)} \equiv 1 \pmod m

:::::success[证明]

构造 m 的既约剩余系 S=\{x_1,x_2,\cdots,x_{\varphi(m)}\},并将每个元素乘 a 得到新的集合 S'=\{ax_1,ax_2,\cdots,ax_{\varphi(m)}\}。

下证:S 和 S' 在模 m 意义下相等。

既然 S 与 S' 同余,则所有元素的乘积模 m 也同余:

\begin{aligned} \prod_{i=1}^{\varphi(m)} x_i &\equiv \prod_{i=1}^{\varphi(m)} a x_i \pmod m\\ \prod_{i=1}^{\varphi(m)} x_i &\equiv a^{\varphi(m)}\prod_{i=1}^{\varphi(m)} x_i \pmod m \end{aligned}

由 \gcd(x_i,m)=1 可知 \prod\limits_{i=1}^{\varphi(m)} x_i 存在逆元,同余式两边约去即得

a^{\varphi(m)}\equiv 1 \pmod m

证毕。

:::::

用质数 p 代替欧拉定理中的 m,则 \gcd(a,p)=1 自然成立,代入上式即得

费马小定理 若 p 为质数,则

a^{p-1} \equiv 1 \pmod p

注意到 a 在模 p 意义下有逆元,因此有如下两个变形式:

第二条变形式给出了模 p 意义下 a 的逆元,可以直接快速幂 O(p) 计算。

5.2 Dirichlet 卷积

数论函数 f 和 g 的 Dirichlet 卷积定义为

(f \ast g)(n)=\sum_{k \mid n} f(k) g\left(\frac{n}{k}\right)

Dirichlet 卷积满足如下性质:

进一步,全体积性函数对 Dirichlet 卷积和 Dirichlet 逆封闭:

从 Dirichlet 卷积的观点来看,我们可以得到如下结论:

结论 1

\epsilon = \mu \ast \mathbf{1} \iff \epsilon(n)=\sum_{d \mid n} \mu(d)

这表明,\mu 是 \mathbf{1} 的 Dirichlet 逆。常见的应用是

[a \perp b]=\sum_{d \mid a, d \mid b} \mu(d)

这个式子可以转化 \gcd(a,b)=1 的条件,有利于交换求和顺序,通过进一步推导降低复杂度。

结论 2

\text{id}=\varphi \ast \mathbf{1} \iff n=\sum_{d \mid n} \varphi(d)

这个式子又被称为 Euler 反演。一个常见的推论是

\gcd(a,b)=\sum_{d \mid a, d \mid b} \varphi(d)

结论 3

\tau = \mathbf{1} \ast \mathbf{1} \iff \tau(n)=\sum_{d \mid n} 1

结论 4

\sigma = \text{id} \ast \mathbf{1} \iff \sigma(n)=\sum_{d \mid n} d

结论 5

\varphi = \text{id} \ast \mu \iff \varphi(n)=\sum_{d \mid n} d \mu \left(\dfrac{n}{d}\right)

考虑更一般的情形,对两个数论函数 f,g,我们有

f = \mathbf{1} \ast g \iff g = \mu \ast f

:::::success[证明]

将等式两边同时卷积 \mu 得

f \ast \mu = \mathbf{1} \ast \mu \ast g=g

:::::

代入 Dirichlet 卷积的定义式得

f(n)=\sum_{d \mid n} g(d) \iff g(n) = \sum_{d \mid n} \mu\left(\dfrac{n}{d}\right) f(d)

这就是著名的 Möbius 反演。

利用 Möbius 反演可以推导出另一些有用的结论。例如,对 \sigma_k =\text{id}_k \ast \mathbf{1} 做 Möbius 反演得

结论 6

\text{id}_k = \mu \ast \sigma_k \iff n^k = \sum_{d \mid n} \mu \left(\dfrac{n}{d}\right) \sigma_k(d)

5.3 练习

P2398 GCD SUM

给定 n,求

\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)

:::::success[Euler 反演]

对 \gcd(i,j) 做 Euler 反演

\begin{aligned} \sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)&= \sum_{i=1}^n \sum_{j=1}^n \sum_{d \mid i, d \mid j} \varphi(d)\\ &= \sum_{d=1}^n \varphi(d) \sum_{d \mid i, i \le n} \sum_{d \mid j, j \le n}1\\ &= \sum_{d=1}^n \varphi(d) \left\lfloor \dfrac{n}{d}\right\rfloor^2 \end{aligned}

预处理 \varphi 的前缀和后,二维数论分块即可,复杂度 O(\sqrt{n})。

:::::

:::::success[Möbius 反演]

首先

\begin{aligned} \sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)&=\sum_{k=1}^n k \sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j)=k] \end{aligned}

转而枚举 \dfrac{i}{k} 和 \dfrac{j}{k} 得

\begin{aligned} \sum_{k=1}^n k \sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j)=k] &= \sum_{k=1}^n k \sum_{i=1}^{ \lfloor n/k \rfloor}\sum_{j=1}^{ \lfloor n/k \rfloor} [\gcd(i,j)=1]\\ &= \sum_{k=1}^n k \sum_{i=1}^{ \lfloor n/k \rfloor}\sum_{j=1}^{ \lfloor n/k \rfloor} \sum_{d \mid i, d \mid j} \mu(d)\\ &=\sum_{k=1}^n k \sum_{d=1}^n \mu(d) \sum_{d \mid i, i \le \lfloor n/k \rfloor} \sum_{d \mid j, j \le \lfloor n/k \rfloor} 1\\ &= \sum_{k=1}^n k \sum_{d=1}^n \mu(d) \left\lfloor \dfrac{n}{kd}\right\rfloor^2\\ \end{aligned}

转而枚举 a=kd 得

\begin{aligned} \sum_{k=1}^n k \sum_{d=1}^n \mu(d) \left\lfloor \dfrac{n}{kd}\right\rfloor^2&=\sum_{a=1}^n \left\lfloor \dfrac{n}{a} \right\rfloor^2 \sum_{k \mid a} k \mu\left(\dfrac{a}{k}\right) \\ &=\sum_{a=1}^n \varphi(a) \left\lfloor \dfrac{n}{a} \right\rfloor^2 \end{aligned}

预处理 \varphi 的前缀和后,二维数论分块即可,复杂度 O(\sqrt{n})。

:::::

:::::success[数论容斥]

首先

\begin{aligned} \sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)&=\sum_{k=1}^n k \sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j)=k] \end{aligned}

设 f(k)=\sum\limits_{i=1}^n \sum\limits_{j=1}^n [\gcd(i,j)=k],并记 g(k)=\sum\limits_{i=1}^n \sum\limits_{j=1}^n [k \mid \gcd(i,j)],f \to g 的转化为

g(k)=\sum_{i=1}^{\lfloor n/k\rfloor} f(ik)

考察 g 的定义

\begin{aligned} g(k)&=\sum\limits_{i=1}^n \sum\limits_{j=1}^n [k \mid \gcd(i,j)]\\ &=\sum_{i=1}^n \sum_{j=1}^n [k \mid i][k \mid j]\\ &= \left\lfloor \dfrac{n}{k} \right\rfloor^2 \end{aligned}

观察 f \to g 的式子即得 g \to f 的转化

f(k)=g(k)-\sum_{i=2}^{\lfloor n/k \rfloor} f(ik)

倒序枚举 k 并计算 f 即可,这是一个调和型枚举,复杂度 O(n \log n)。

:::::

P2522 [HAOI2011] Problem b

给定 a,b,c,d,k,求

\sum_{i=a}^b \sum_{j=c}^d [\gcd(i,j)=k]

多测,T \le 5 \times 10^4,a,b,c,d,k \le 5 \times 10^4,2.5 秒,250 MB。

:::::success[题解]

容易用二维差分将问题变为求解

f(n,m)=\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=k]

不妨设 n\le m,转为枚举 \dfrac{i}{k} 和 \dfrac{j}{k} 得

\begin{aligned} f(n,m)&= \sum_{i=1}^{\lfloor n/k \rfloor} \sum_{j=1}^{\lfloor m/k \rfloor} [\gcd(i,j)=1]\\ &=\sum_{i=1}^{\lfloor n/k \rfloor} \sum_{j=1}^{\lfloor m/k \rfloor} \sum_{d \mid i, d \mid j} \mu(d)\\ &= \sum_{d=1}^n \mu(d) \sum_{i \mid d, i \le \lfloor n/k \rfloor} \sum_{j \mid d, j \le\lfloor m/k \rfloor} 1\\ &= \sum_{d=1}^n \mu(d) \left\lfloor \dfrac{n}{kd} \right\rfloor\left\lfloor \dfrac{m}{kd} \right\rfloor\\ \end{aligned}

预处理 \mu 的前缀和,二维数论分块即可。复杂度 O(n + T \sqrt{n})。

:::::

:::::info[代码]

const int N = 5e4 + 5;
bitset<N> s;
vector<int> p;
i64 mu[N];
void prework() {
    s.set(), s[1] = 0, mu[1] = 1;
    for (int i = 2; i < N; i++) {
        if (s[i]) mu[i] = -1, p.emplace_back(i);
        for (int j : p) {
            if (i * j >= N) break;
            s[i * j] = 0;
            if (i % j == 0) {
                mu[i * j] = 0; break;
            }
            mu[i * j] = -mu[i];
        }
    }
    for (int i = 1; i < N; i++) mu[i] += mu[i - 1];
}

i64 f(int n, int m, int k) {
    n /= k, m /= k;
    if (n <= 0 || m <= 0) return 0;
    if (n < m) swap(n, m);
    i64 res = 0;
    for (int l = 1, r; l <= m; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        res += (mu[r] - mu[l - 1]) * (n / l) * (m / l);
    } return res;
}

void _main() {
    int q; cin >> q; prework();
    for (int a, b, c, d, k; q--; ) {
        cin >> a >> b >> c >> d >> k;
        cout << f(b, d, k) - f(a-1, d, k) - f(b, c-1, k) + f(a-1, c-1, k) << '\n';
    }
}

:::::

P3327 [SDOI2015] 约数个数和

给定 n,m,求

\sum_{i=1}^n \sum_{j=1}^m \sigma(ij)

多测,T \le 5 \times 10^4,n,m \le 5 \times 10^4,1 秒,125 MB。

:::::success[题解]

注意到如下事实

\sigma(ij)=\sum_{x \mid i} \sum_{y \mid j} [x \perp y]

不妨设 n \le m,代入所求

\begin{aligned} \sum_{i=1}^n \sum_{j=1}^m \sigma(ij)&=\sum_{i=1}^n \sum_{j=1}^m\sum_{x \mid i} \sum_{y \mid j} [x \perp y]\\ &=\sum_{i=1}^n \sum_{j=1}^m\sum_{x \mid i} \sum_{y \mid j} \sum_{d \mid x, d \mid y} \mu(d)\\ &=\sum_{d=1}^n \mu(d) \sum_{i=1}^n \sum_{j=1}^m\sum_{d \mid x, x \mid i} \sum_{d \mid y, y \mid j} 1 \end{aligned}

套路地,转而枚举 \dfrac{i}{d} 和 \dfrac{j}{d} 得

\begin{aligned} &\sum_{d=1}^n \mu(d) \sum_{i=1}^n \sum_{j=1}^m\sum_{d \mid x, x \mid i} \sum_{d \mid y, y \mid j} 1\\ =& \sum_{d=1}^n \mu(d) \sum_{i=1}^{\lfloor n/d \rfloor} \sum_{j=1}^{\lfloor m/d \rfloor} \left\lfloor \dfrac{n}{id} \right\rfloor \left\lfloor \dfrac{m}{jd} \right\rfloor\\ =& \sum_{d=1}^n \mu(d) \left(\sum_{i=1}^{\lfloor n/d \rfloor} \left\lfloor \dfrac{n}{id} \right\rfloor \right) \left(\sum_{j=1}^{\lfloor m/d \rfloor} \left\lfloor \dfrac{m}{jd} \right\rfloor\right) \end{aligned}

记 f(x)=\sum\limits_{i=1}^{x} \left\lfloor \dfrac{x}{i} \right\rfloor 代入上式

\begin{aligned} &\sum_{d=1}^n \mu(d) \left(\sum_{i=1}^{\lfloor n/d \rfloor} \left\lfloor \dfrac{n}{id} \right\rfloor \right) \left(\sum_{j=1}^{\lfloor m/d \rfloor} \left\lfloor \dfrac{m}{jd} \right\rfloor\right)\\ =& \sum_{d=1}^n \mu(d) f\left(\left\lfloor\dfrac{n}{d}\right\rfloor\right) f\left(\left\lfloor\dfrac{m}{d}\right\rfloor\right) \end{aligned} ::::: :::::info[代码] ```cpp line-numbers const int N = 5e4 + 5; bitset<N> s; vector<int> p; i64 mu[N], f[N]; void prework() { s.set(), s[1] = 0, mu[1] = 1; for (int i = 2; i < N; i++) { if (s[i]) mu[i] = -1, p.emplace_back(i); for (int j : p) { if (i * j >= N) break; s[i * j] = 0; if (i % j == 0) { mu[i * j] = 0; break; } mu[i * j] = -mu[i]; } } for (int i = 1; i < N; i++) mu[i] += mu[i - 1]; auto cal = [&](int n) -> i64 { i64 res = 0; for (int l = 1, r; l <= n; l = r + 1) { r = min(n, n / (n / l)); res += (n / l) * (r - l + 1); } return res; }; for (int i = 1; i < N; i++) f[i] = cal(i); } void _main() { int q; cin >> q; prework(); for (int n, m; q--; ) { cin >> n >> m; if (n > m) swap(n, m); i64 res = 0; for (int l = 1, r; l <= n; l = r + 1) { r = min(n / (n / l), m / (m / l)); res += (mu[r] - mu[l - 1]) * f[n / l] * f[m / l]; } cout << res << '\n'; } } ``` ::::: ### [P1829 [集训队互测 2010] Crash的数字表格 / JZPTAB](https://www.luogu.com.cn/problem/P1829) > 给定 $n,m$,求 > $$ > \left( \sum_{i=1}^n \sum_{j=1}^m \text{lcm}(i,j)\right) \bmod 20101009 > $$ > $n,m \le 10^7$,2 秒,500 MB。 :::::success[题解] 不妨设 $n \le m$。代入 $\text{lcm}$ 的性质式,推式子 $$ \begin{aligned} \sum_{i=1}^n \sum_{j=1}^m \text{lcm}(i,j) &= \sum_{i=1}^n \sum_{j=1}^m \dfrac{ij}{\gcd(i,j)}\\ &= \sum_{k=1}^n \sum_{i=1}^n \sum_{j=1}^m ij[\gcd(i,j)=k] \\ \end{aligned} $$ 套路地枚举 $\dfrac{i}{k}$ 和 $\dfrac{j}{k}$ 得 $$ \begin{aligned} \sum_{k=1}^n k \sum_{i=1}^n \sum_{j=1}^m ij[\gcd(i,j)=k] &= \sum_{k=1}^n k \sum_{i=1}^{\lfloor n/k \rfloor} \sum_{j=1}^{\lfloor m/k \rfloor} ij [\gcd(i,j)=1]\\ &=\sum_{k=1}^n k \sum_{i=1}^{\lfloor n/k \rfloor} \sum_{j=1}^{\lfloor m/k \rfloor} ij \sum_{d \mid i, d \mid j} \mu(d)\\ &= \sum_{k=1}^n k \sum_{d=1}^{\lfloor n/k \rfloor} \mu(d) \sum_{d \mid i, i\le \lfloor n/k \rfloor} \sum_{d \mid j, j \le \lfloor m/k \rfloor} ij \end{aligned} $$ 转而枚举 $\dfrac{i}{d}$ 和 $\dfrac{j}{d}$,注意这里的 $i,j$ 是上式的下指标,即原本的 $\dfrac{i}{k}$ 和 $\dfrac{j}{k}$。 $$ \begin{aligned} &\sum_{k=1}^n k \sum_{d=1}^{\lfloor n/k \rfloor} \mu(d) \sum_{d \mid i, i\le \lfloor n/k \rfloor} \sum_{d \mid j, j \le \lfloor m/k \rfloor} 1\\ =&\sum_{k=1}^n k \sum_{d=1}^{\lfloor n/k \rfloor}d^2 \mu(d) \sum_{i=1}^{\lfloor n/kd \rfloor} \sum_{j=1}^{\lfloor m/kd \rfloor} ij\\ =&\sum_{k=1}^n k \sum_{d=1}^{\lfloor n/k \rfloor}d^2 \mu(d) \left(\sum_{i=1}^{\lfloor n/kd \rfloor} i\right)\left( \sum_{j=1}^{\lfloor m/kd \rfloor}j\right)\\ =&\sum_{k=1}^n k \sum_{d=1}^{\lfloor n/k \rfloor}d^2 \mu(d) \binom{\lfloor n/kd \rfloor}{2}\binom{\lfloor m/kd \rfloor}{2} \end{aligned} $$ 将内层求和视为有关 $\lfloor n/k \rfloor$ 的函数,预处理 $d^2 \mu(d)$ 的前缀和后,内层求和可用二维数论分块优化。 外层求和同样使用二维数论分块优化。嵌套数论分块的复杂度为 $O(n^{3/4})$,此时复杂度瓶颈在线性筛的 $O(n)$。 ::::: :::::info[代码] ```cpp line-numbers const int N = 1e7 + 5; int n, m; bitset<N> s; vector<int> p; int mu[N]; mint pre[N]; void prework() { s.set(), s[1] = 0, mu[1] = 1; for (int i = 2; i <= n; i++) { if (s[i]) mu[i] = -1, p.emplace_back(i); for (int j : p) { if (i * j >= N) break; s[i * j] = 0; if (i % j == 0) { mu[i * j] = 0; break; } mu[i * j] = -mu[i]; } } for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + 1LL * i * i * mu[i]; } const mint i2 = ~mint(2); mint sum(mint x) {return x * (x + 1) * i2;} mint work(int n, int m) { if (n > m) swap(n, m); mint res = 0; for (int l = 1, r; l <= n; l = r + 1) { r = min(n / (n / l), m / (m / l)); res += sum(n / l) * sum(m / l) * (pre[r] - pre[l - 1]); } return res; } void _main() { cin >> n >> m; if (n > m) swap(n, m); prework(); mint res = 0; for (int l = 1, r; l <= n; l = r + 1) { r = min(n / (n / l), m / (m / l)); res += (sum(r) - sum(l - 1)) * work(n / l, m / l); } cout << res; } ``` :::::