数论基础

发表于

数论基础

作为一门研究整数性质的哲学，数论在 OI 中还是很受欢迎的，它凭借着它别具一格的特色和令人……

我编不下去了，开始研究数论。。

一些小知识

  • 若 $b % a = 0$ 即 $b = ka$ ，则我们成 $a$ 整除 $b$ ，记作 $a | b$ 。

  • 若 $a | b$ ，则我们称 $a$ 为 $b$ 的一个因数(或约数)。

  • 若 $a | b$ 且 $a | c$ ，则我们称 $a$ 为 $b$ 和 $c$ 的公因数，如果 $a$ 为 $b$ 和 $c$ 所有公因数中最大的，则我们称 $a$ 为 $b$ 和 $c$ 的最大公约数。

  • 如果 $a % c = b % c$ ，则我们称在 $\mod c$ 下 $a$ 与 $b$ 同余，记作 $a ≡ b \mod c$ 。同时这个也称作 $c$ 的同余系。

  • 如果 $\gcd(a, b) = 1$ 则称 $a$ 与 $b$ 互质。

欧几里德算法

我们用 $\gcd(a, b)$ 代表 $a$ 和 $b$ 的最大公约数，那么它具有如下性质： $\gcd(a, b) = \gcd(b, a % b)$ 。

证明如下：

显然我们如果证明出来 $\gcd(a, b)$ = $\gcd(a, b + a)$ 即可证明此性质，因为显然 $\gcd(a, b) = \gcd(b, a)$ 。

我们设 $k = \gcd(a, b)$ ，则我们设 $a = km$, $b = kn$ 。 则 $a + b = k(m + n)$ ，如此我们可以证明 $a$, $b$ 的最大公因数是 $a$, $b + a$ 的公因数 (显然， $k | (a + b)$ 且 $k | a$ ) 。 那么如何证明 $k$ 是 $a$, $b + a$ 的最大公约数呢？

我们假设 $k$ 不是 $a$, $b + a$ 的最大公约数，则 $a$, $b + a$ 一定存在一个最大公约数 r 满足 $r > k$ 。则我们设 $a = rc$, $b + a = rv$ 则 $b = b + a - a = r(v - c)$ 则 $a$, $b$ 存在公约数 $r$ 且 $r > k$， 这与 $k$ 是 $a$, $b$ 的最大公约数相矛盾，所以 $k$ 为 $a$ 和 $b + a$ 的最大公约数。

证明出来了这一点我们就可以放心地写 gcd 的代码了：

1
2
3
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

欧几里得算法的时间复杂度为 O(log(a + b)) 。

显然当 a 和 b 为 Fibnacci 数列相邻两项时 gcd 需要的计算次数最多， 分析 Fibnacci 数列的通项公式，我们可以得知对于计算 n 次的欧几里得算法，其 a 和 b 的上界为 Fib[a + b]， 如此，我们就可以简单说明其复杂度为 log 级别的。

拓展欧几里德

欧几里得算法是一个非常神奇的算法，当然是有大用处的，我们可以用来解决像 $ax + by = c$ 的不定方程求整数解问题，我们分析如何来求解。

我们先来分析对于某个解，我们如何求出其他解。

即我们知道了 $ax_0 + by_0 = c$ 。

则 $a(x_0 + b - b) + by_0 = c$

$a(x_0 + b) + b(y_0 - a) = c$

即我们如果知道了一组解 $x_0$, $y_0$ ，我们可以通过将 $x_0$ 增加若干的 $b$ 而 $y_0$ 增加相同数目的 $a$ 来找出另一组解，即我们知道其中一组解就可以知道所有解。

接下来我们考虑如何求出其中一组解。

对于方程 $ax + by = c$ ，其有解的充要条件是 $\gcd(a, b) | c$ ，这是显而易见的，起码对于必要条件如此。所以说，我们可以将两边同时除以 $c$ ，就可以转变为 $ax + by = 1$ 了。

接下来，我们对于 $ax + by = 1$ 这个方程讨论解。

我们设 $a = kb + r$ ，其中 $0 \leq r < b$， 即 $k = ⌊a / b⌋$, $r = a % b$ 。

根据某个奇奇怪怪的定理，这样分解的 k 和 r 都是唯一的，这显然是显然的。

之后方程就变成了 $(kb + r)x + by = 1$

$b(kx + y) + rx = 1$

接下来我们将 $b$ 看做新的 $a$ ，将 $(kx + y)$ 看做新的 $x$ ， 将 $r$ 看做新的 $b$ ，将 $x$ 看做新的 $y$ ，对这个方程进行求解，求完解之后我们转化为当前的 $x$ 和 $y$ 即可。

直到最后， $b$ 会变成 $0$ ，这时候就变成了 $ax = 1$ 的形式，这个时候若 $a = 1$ 则表示有解，且 $x$ 为 $1$ ， $y$ 我们让它等于 $0$ 就好啦，其实这里 $y$ 等于什么并不会影响结果的正确性，只是求出来的解不一样而已。并且这个时候 $a$ 就是最开始的时候 $a$ 和 $b$ 的最大公约数。

所以我们就可以贴出代码了：

1
2
3
4
5
int exgcd(int a, int b, int &x, int &y){
    if(b == 0) return x = 1, y = 0, a;
    int r = exgcd(b, a % b, y, x);
    return y -= a / b * x, r;
}

线性同余方程

接下来，我们需要对 $ax ≡ 1 \mod b$ 的解。

显然这个方程就是 $ax % b = 1$ 也就是对 $ax + by = 1$ (注意这里 $y$ 一般是负数，若 $a > b$)。

显然这个方程有解的充要条件是 $\gcd(a, b) = 1$ 。

我们对不定方程求解即可得到这个同余方程的解。

逆元

我们对于一个数 $a$ ，如果存在一个整数 $b$ 使得 $ab ≡ 1 \mod p$ 则称 $b$ 是 $a$ 的逆元，记作 $a^{-1}$。

所以我们显然可以用拓展欧几里得来求出一个数的逆元，也就是对 $a×a^{-1} ≡ 1 \mod p$ 进行求解。

然而我们还有一个更加方便的方法，就是利用费马小定理，当 $p$ 是质数的时候 $a^{-1} ≡ a^{p - 1} \mod p$。这样的话我们可以用快速幂来进行求解。

以上求解逆元的方法都是 O(log a) 的，那么我们有没有一种方法可以在 O(n) 的时间内求出 $1-n$ 的所有逆元呢？

线性求逆元

我们考虑取模的定义式

$p % a = p - ⌊p / a⌋ × a$

我们将其放在 $p$ 的同余系下

$p % a ≡ - ⌊p / a⌋ × a \mod p$

我们在两边同时乘以 $(p % a)^{-1}a^{-1}$

$a^{-1} ≡ -⌊p / a⌋ × (p % a)^{-1} \mod p$

因为 $p % a$ 肯定是小于 $a$ 的，所以当我们知道了 $1～(a - 1)$ 所有数的逆元，我们就可以在 O(1) 时间复杂度内求出 $a$ 的逆元。

所以说代码也是极短，其中 $p$ 是要 mod 的数

1
2
3
4
5
void GetInv(int n){
    inv[1] = 1;
    for(int i = 2; i <= n; i++)
        inv[i] = -p / a * inv[p % a] % p + p;
}

(CRT) 中国剩余定理

我们考虑过了对 $ax ≡ 1 \mod p$ 进行求解，但是对于线性同余方程组我们如何进行求解呢？这就需要 CRT 了， CRT 全称 Chinese Remainder Theorem ，叫中国剩余定理，讲解了如何构造同余线性方程组的解。

我们考虑对于线性同余方程组

$x ≡ a_1 \mod m_1$

$x ≡ a_2 \mod m_2$

$\dots$

$x ≡ a_n \mod m_n$

我们可以设 $M = \prod_\limits{i = 1}^na_i$， 令 $M_i = M / m_i$， $t_i = M_i^{-1} \mod m_i$ 。

如此，我们就可以构造出解 $x$ 为 $\sum_\limits{i = 1}^na_it_iM_i$ 。

这样构造出来的答案的正确性是显然的，每一个 $M_it_ia_i$ 对于 $\mod mi$ 为 $a_i$ ，对于其他的 $m$ 则取模后为 $0$ ，将每一个 $M_it_ia_i$ 简单相加即可构造答案。

另外对于模数不互质的情况，我们便无法通过此种方式求解了，我们可以采用一种合并两个方程为一个方程的方式求解。

考虑如何把两个方程转化为一个方程：

$$ x ≡ a_1 \mod m_1 $$
$$ x ≡ a_2 \mod m_2 $$
由方程可知
$$ x = k_1m_1 + a_1 $$
$$ x = k_2m_2 + a_2 $$
$$ k_1m_1 + a_1 = k_2m_2 + a_2 $$
$$ k_1m_1 ≡ a_2 - a_1 \mod m_2 $$

令 $d = \gcd(m1, m2)$，$c = a_2 - a_1$

$$ \frac{m_1}dk_1 ≡ \frac cd \mod \frac{m_2}d $$
$$ k_1 ≡ \frac cd \times (\frac{m_1}d)^{-1} \mod \frac{m_2}d $$

令 $K = \frac cd \times (\frac{m_1}d)^{-1}$

$$ k_1 = p\frac{m_2}d + K $$
$$ x = p\frac{m_1m_2}d + m_1K + a_1 $$
$$ x ≡ m_1K + a_1 \mod \frac{m_1m_2}d $$

欧拉函数

欧拉函数 $\phi$ 为数论中的一个很重要的函数。我们定义 $\phi(n)$ 为 $1-n$ 中与 $n$ 互质的数的个数。

即我们可以说 ：

$$ \phi(n) = \sum_{i = 1}^n[\gcd(i, n) = 1] $$

接下来我们考虑如何求 $\phi(n)$

我们设 $n = p_1^{k_1} × p_2^{k_2} × p_3^{k_3} × \dots$

其中 $p_1, p_2, p_3, \dots$ 为质数。

则 $\phi(n) = n×(1 - \frac1{p_1})×(1 - \frac1{p_2})×\dots$

即在 $1 - n$ 中能被 $p_1$ 整除的占 $\frac1{p_1}$ 则不能被 $p_1$ 整除的占 $1 - \frac1{p_1}$， $n$ 乘上 $1 - \frac1{p_1}$ 即为不能被 $p_1$ 整除的数的个数。

所以我们可以把求 $\phi$ 的套在质因数分解里边，即：

1
2
3
4
5
6
7
8
9
int phi(int x){
    int ret = x;
    for(int i = 2; i * i <= x; i++){
        if(x % i == 0) ret /= i, ret *= i - 1;
        while(x % i == 0) x /= i;
    }
    if(x > 1) ret /= x, ret *= x - 1;
    return ret;
}

线性筛

线性筛可以在 O(n) 的时间复杂度内求出 $1 - n$ 之内的所有素数，还可以筛出许多积性函数的值，如 $\phi$，$\mu$ 等。

我们先贴出代码，来分析一下为什么其时间复杂度为 O(n) 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Shaker(int n){
    int cnt = 0;
    notPrime[1] = 1, phi[1] = 1;
    for(int i = 2; i <= n; i++){
        if(!notPrime[i]) prime[cnt++] = i, phi[i] = i - 1;
        for(int j = 0; j < cnt && prime[j] * i <= n; j++){
            notPrime[prime[j] * i] = 1;
            if(i % prime[j] == 0){
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}

这里我们加入了求 $\phi$ 的过程，其他地方都是很显然的，但是对于

1
phi[i * prime[j]] = phi[i] * prime[j];

这一句可能不是很好理解，具体说明会在下面给出。

我们可以注意到如果 $i % prime[j] = 0$ 的话我们跳出循环，正是因为这个剪枝才造成了其 O(n) 的时间复杂度。

即如果 $i % prime[j] = 0$，那么再往后循环的 $i * prime[j]$ 一定会被当前的 $prime[j]$ 筛掉，故可以 break 掉。

我们亦可将求 $\mu$ 的代码插入其中，即：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Shaker(){
	mu[1] = 1;
	for(int i = 2; i <= 500000; i++){
		if(!not_prime[i]){
			mu[i] = -1;
			prime[++tot] = i;
		}
		for(int j = 1; j <= tot && i * prime[j] <= 50000; j++){
			not_prime[i * prime[j]] = true;
			if(i % prime[j] == 0){
				mu[i * prime[j]] = 0;
				break;
			}
			mu[i * prime[j]] = -mu[i];
		}
	}
}

即可线性求 $\mu$。

另外对于线性求 $\phi$ 的一点，即

1
2
if(i % prime[j] == 0)
    phi[i * prime[j]] = phi[i] * prime[j];

可能并不是非常显然。我们在证明 $\gcd$ 时提到过 $\gcd(a + b, b) = \gcd(a, b)$ ，即可理解为若 $a$ 与 $b$ 互质，则 $a + b$ 与 $b$ 互质，否则反之。

若 $i % p = 0$, 则表示一个数若与 $i$ 互质，则与 $i * p$ 互质，否则反之。

故在区间 $[1, i \times p]$ 中与 $i \times p$ 互质的数的个数为 $\phi(i) \times p = \phi(i \times p)$。

莫比乌斯反演

在说反演之前我们先说一下狄利克雷(Dirichlet)卷积。

定义两个数论函数的狄利克雷卷积如下：

$$ (f * g)(n) = \sum_{d|n}f(d)g(\frac nd) $$

狄利克雷卷积遵循交换律，结合律和分配律。

显然地，若 $f，g$ 均为积性函数，$f * g$ 也为积性函数。

我们设一个单位函数 $e(n) = \begin{cases}
1 && n = 1 \
0 && n > 1
\end{cases}$

，我们把 $e$ 称作 $1$。

另外对于莫比乌斯函数 $\mu$ 的定义为:

$$\mu(n) = \begin{cases}
1 && n = 1\
(-1)^k && n = p_1p_2\dots p_k\
0 && else
\end{cases}$$

然后我们可以证明：

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

我们来看莫比乌斯反演，若有两个函数 $f，g$ 满足：

$$ f(n) = \sum_{d|n}g(d) $$

则它们也满足

$$ g(n) = \sum_{d|n}\mu(d)f(\frac nd) $$

我们可以利用卷积很容易地证明这个公式，即

$$ f = g * 1 $$

我们在两边同时乘上 $\mu$ 即可得到

$$ g = \mu * f $$

即为所求。

这个公式即为莫比乌斯反演的公式，这个公式可以极大简化计算，比较重要。