数论函数
stripe_python
·
·
算法·理论
5. 数论函数
我们给出如下定义:
- 数论函数 f 是一个映射 f:\mathbb{N}^{+} \to \mathbb{C}。
- 若数论函数 f 满足 f(1)=1,且 \forall x \perp y, f(xy)=f(x) f(y),则称 f 是积性函数。
- 若数论函数 f 满足 f(1)=1,且 \forall x,y, f(xy)=f(x) f(y),则称 f 是完全积性函数。
积性函数对乘法封闭:
- 若 f,g 是积性函数,则 f \times g 也是积性函数。
常见的积性函数:
- Dirichlet 卷积单位元:\epsilon(n)=[n=1],完全积性。
- 幂函数:\text{id}_k(n)=n^k,完全积性。将 \text{id}_1(n) 简记为 \text{id}(n)。
- 常值函数:\mathbf{1}(n)=1,完全积性。
- 除数函数:\tau(n) 为 n 的因子数目,也写为 d(n)。
- 因子和函数:\sigma_{k}(n)=\sum \limits_{d \mid n} d^k。将 \sigma_1(n) 简记为 \sigma(n)。
- 欧拉函数:\varphi(n) 定义为 [1,n] 内与 n 互质的数的数目,即 \varphi(n)=\sum \limits_{i=1}^n [i \perp n]。
- Möbius 函数:\mu(n) 是 \mathbf{1} 的 Dirichlet 逆。
- 若 n=1,则 \mu(n)=1。
- 若 n 存在 >1 的平方因子,则 \mu(n)=0。
- 否则,设 k 为 n 的质因子数,\mu(n)=(-1)^k。
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 意义下相等。
- 封闭性:由于 \gcd(a,m)=1 且 \gcd(x_i,m)=1,必有 \gcd(ax_i,m)=1,即 ax_i \bmod m \in S。
- 不重性:反证法,若存在两个元素 i,j \in S' 同余,则有 ax_i \equiv ax_j \pmod m。显然 a 的逆元存在,故 x_i \equiv x_j \pmod m,与 S 是既约剩余系矛盾。故 S' 不重。
既然 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 卷积满足如下性质:
-
交换律:f \ast g = g \ast f。
-
结合律:(f \ast g) \ast h=f \ast (g \ast h)。
-
分配律:(f+g) \ast h= f \ast h+g \ast h。
-
单位元:f \ast \epsilon = \epsilon \ast f=f。
-
逆元:当且仅当 f(1) \ne 0 时,\exists g, f \ast g = g \ast f = \epsilon,将 g 记作 f^{-1}。
进一步,全体积性函数对 Dirichlet 卷积和 Dirichlet 逆封闭:
- 若 f,g 是积性函数,则 f \ast g 也是积性函数。
- 逆元 f^{-1} 必然存在,且 f^{-1} 也是积性函数。
从 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;
}
```
:::::