数论,但是板子

时间:2023-02-24 21:04:24

你猜为什么我数学那么差?

1. 从欧几里得算法到扩展欧几里得算法

我们一般用欧几里得算法求最大公约数,它差不多就这样

\(\gcd(m, n) = \begin{cases}n&m = 0\\\gcd(n, m \bmod n) & (m \not = 0)\end{cases}\)

扩欧可以用来求这个:\(ax + by = \gcd(a, b)\) 的正整数解 \(x, y\)。我们用欧几里得算法来迭代求解,我们得出来的解满足 \(|x|+|y|\) 最小。

\(b = 0\) 时,\(\gcd(a, b) = a\),因此 \(x = 1, y = 0\),其实 \(y\) 可以是任意一个数字(因为 \(b = 0\)),但是由于我们要求的是 \(|x|+|y|\) 最小的解,所以 \(y = 0\)

接下来假设我们已经求出来了 \(bx+ (a\bmod b)y = \gcd(a, b)\),从这一步再求 \(ax'+by' = \gcd(a, b)\) 的解(相当于递归回来做),\(a\bmod b = a - \lfloor\dfrac{a}{b}\rfloor b\),所以就有
\(bx+(a\bmod b)y = bx+(a - \lfloor\dfrac{a}{b}\rfloor b)y = ay + b(x - \lfloor\dfrac{a}{b}\rfloor y)\),也就是说 \(x' = y, y' = x - \lfloor\dfrac{a}{b}\rfloor y\)

这个玩意儿叫 exgcd


2. 二元一次方程的通解

也就是求 \(ax + by = c\) 这样的方程,通过上面的讨论我们知道只有 \(\gcd(a, b)|c\) 这样的方程才有整数解,为了方便叙述下面记 \(d = \gcd(a, b)\)

首先用 exgcd 求出 \(ax' + by' = d\) 的一对解 \(x', y'\),然后容易得到原方程 \(ax+by = c\) 的通解形式是 \(\begin{cases}x = x'\dfrac{c}{d}+k\dfrac{b}{d}\\ y = y'\dfrac{c}{d} - k\dfrac{a}{d} \end{cases}\)。记 \(\dfrac{c}{d} = g\),那么 \(\begin{cases}x = x'g+k\dfrac{b}{d}\\ y = y'g-k\dfrac{a}{d}\end{cases}\) 这样写就好看很多了(雾)

下面让我们来做这道题吧。

Task1 正整数解数量

就是求 \(\begin{cases}x'g+k\dfrac{b}{d}\ge 1 \\ y'g - k\dfrac{a}{d} \ge 1\end{cases}\) 这个不等式组的整数解数量。不难解出来是 \(\dfrac{(1-xg)d}{b}\le k \le \dfrac{(yg - 1)d}{a}\)。由于是整数,所以左边套上向上取整,右边套上向下取整,就得到了 \(\lceil\dfrac{(1-xg)d}{b}\rceil\le k \le \lfloor\dfrac{(yg - 1)d}{a}\rfloor\)。知道取值范围这个就好做了!

Task2 求最大最小解

不难想到 \(x\) 越大 \(y\) 越小,反之亦然,所以 \(k = \lceil\dfrac{(1-xg)d}{b}\rceil\)\(x\) 最小 \(y\) 最大,\(k = \lfloor\dfrac{(yg - 1)d}{a}\rfloor\)\(x\) 最大 \(y\) 最小。

喜闻乐见的代码

//SIXIANG
#include <iostream>
#include <cmath>
#define MAXN 100000
#define int long long
#define QWQ cout << "QWQ" << endl;
using namespace std;
int exgcd(int a, int b, int &x, int &y) {
	if(!b) {x = 1, y = 0; return a;}
	else {
		int rest = exgcd(b, a % b, x, y);
		int tmp = x; x = y, y = tmp - a / b * y;
		return rest;
	}
} 
signed main() {
	int T, a, b, c; cin >> T;
	while(T--) {
		cin >> a >> b >> c;
		
		int x, y, d = exgcd(a, b, x, y);
		if(c % d != 0) {
			cout << -1 << endl;
			continue;
		}
		int g = c / d;
		int L = ceil((double)(1.0 - x * g) * d / (double)(b)), R = floor((double)(y * g - 1.0) * d / (double)(a));
		if(L > R)
			cout << x * g + L * b / d << ' ' << y * g - R * a / d << endl;
		else {
			cout << (R - L + 1) << ' ' << x * g + L * b / d << ' ' << y * g - R * a / d << ' ' << x * g + R * b / d<< ' ' << y * g - L * a / d<< endl;
		}
	}
}

3. 同余与一些关于它的定义

同余就是 \(a\equiv b\pmod m\),它们表示 \(a\)\(b\) 除以 \(m\) 的余数相同,炒个例子,\(6\)\(1\) 关于 \(5\) 同余,就可以写成 \(6\equiv 1 \pmod 5\)

如果 \(a\equiv b \pmod m\),那么 \((a+c)\equiv (b+c)\pmod m\\ ac\equiv bc\pmod m \\ \dfrac{a}{c}\equiv \dfrac{b}{c}\pmod m(c|a, c|b)\)

同余有如下性质:\((a+b)\equiv (a\bmod m+b\bmod m)\pmod m\\(a-b)\equiv (a\bmod m - b\bmod m)\pmod m\\(a\times b)\equiv (a\bmod m \times b \bmod m) \pmod m\)

除法就没有这样的性质了。我们要单独讨论它,方法是求逆元,还要用上别的知识,一般用 exgcd/费马小定理求逆元,还有线性的方法(不过好像用得不多?)

剩余系:模 \(n\) 的完全剩余系是一个集合 \(Z_n\),这个集合是 \(Z_n =\{0, 1, 2, 3, \dots, n - 1\}\)。这里面的元素不是普通的元素,这里面的每个数代表所有与它同余的整数。举个例子,\(Z_7\),这里面的 \(6\) 元素代表的是 \(6, 13, 20\dots\)

简化剩余系(也叫缩系):将 \(Z_n\) 里面只保留与 \(n\) 互质的数,记为 \(Z_n'\)(可能不是很规范 qwq)比如 \(Z_8' = \{1, 3, 5, 7\}\)

由于它们两个非常的与众不同,所以它们的运算也很与众不同,比如 \(Z_5\)\(3+4 = 2((3+4)\equiv 2 \pmod 5), 3\times 5 = 0((3*5)\equiv 0 \pmod 5)\)

特别的,在简化剩余系里面乘法封闭,意思就是说这里面做乘法的结果还在原来的集合里面,比如 \(Z_8'\) 里面 \(3\times 5 = 7\) 本来就在里面。这个很好证明,如果 \(a\)\(n\) 互质,\(b\)\(n\) 互质,那么 \(ab\)\(n\) 互质。\(\gcd(ab, n) = 1\),根据欧几里得算法所以也有 \(\gcd(ab, n) = \gcd(n, ab\bmod n) = 1\)


4. 欧拉函数的定义

先写一个定义 qwq

请不要认为懂了欧拉函数的定义就啥都明白了,欧拉函数的精髓并不在于它的定义和公式,这里提及完全是为了证欧拉定理费马小定理算逆元(

欧拉函数 \(\varphi(n)\) 定义为 \(1\sim n\) 中与 \(n\) 互质的数个数。比如 \(\varphi(5) = 4\)

我们记 \(n\) 的质因数分别为 \(p_1, p_2, \dots, p_k\)\(\varphi(n) = n(1 - \dfrac{1}{p_1})(1 - \dfrac{1}{p_2})\dots(1 - \dfrac{1}{p_k})\)

证明吗?展开式子,然后就会发现这玩意儿实际上是个容斥,乱搞就能整出来。

这样就可以在 \(O(\sqrt{n})\) 的时间复杂度内求出单个 \(\varphi(n)\)


5. 欧拉定理和费马小定理

其实欧拉函数不应该放在这么前面写的,放在这么前面是为了写一写欧拉定理和费马小定理。

先介绍欧拉定理:\(a^{\varphi(m)}\equiv 1\pmod m\),其中 \(a, m\) 互质。

记得当时看这个的证明一脸懵逼,现在看上去还是很简单的 23333

证明:对于 \(m\) 的简化剩余系 \(Z_n' = \{x_1, x_2, \dots, x_{\varphi(m)}\}\),每个元素同乘一个 \(a\) 得到 \(aZ_n' = \{ax_1, ax_2, \dots, ax_{\varphi(m)}\}\)

由于 \(a\)\(m\) 互质,所以从简化剩余系的角度来看,这两个集合是等价的,所以我们容易得到 \(\prod\limits_{i = 1}^{\varphi(m)}x_i \equiv \prod\limits_{i = 1}^{\varphi(m)}ax_i\pmod m\),也就是 \(\prod\limits_{i = 1}^{\varphi(m)}x_i \equiv \prod\limits_{i = 1}^{\varphi(m)}x_i a^{\varphi(m)}\pmod m\),所以 \(a^{\varphi(m)}\equiv 1 \pmod m\)

感觉这个的证明相当优美啊 qwq!

费马小定理:\(a^{p - 1}\equiv 1 \pmod p\)\(p\) 是质数。

众所周知如果 \(p\) 是质数那么 \(\varphi(p) = p - 1\)。所以其实费马小定理就是欧拉定理的一个推论。

费马小定理用途很广,不仅可以用来做同余,最常见的用途是用来求逆元。


6. 逆元

有的时候我们需要求 \(\dfrac{a}{b}\bmod m\) 的结果,这个时候就不能用常规的方法做了。

逆元可以做这个东西,找到一个 \(x\),使得 \(\dfrac{a}{b} \equiv x\pmod m\)

顺带提一嘴,这里的 \(a, b\) 都是剩余系意义下的,比如说 \(\dfrac{3}{7} \bmod 5\),你会说诶诶诶这压根不是整数它怎么取余再这样下去得输越南,但是实际上这里的 \(3\) 是一个除以 \(5\)\(3\) 的数,\(7\) 同理,这个时候就能整除了。

其实,我们只需要求出一个 \(\dfrac{1}{b} \equiv x\pmod m\)\(x\),那么 \(\dfrac{a}{b}\) 就是两边同乘 \(a\) 的结果,这个 \(x\) 就叫做 \(b\) 在模 \(m\) 意义下的逆元,记作 \(b^{-1}\)\(a / b\) 就是 \(a\times b^{-1}\)

它怎么求?

  1. exgcd
    转化一下 \(xb\equiv 1 \pmod m\),线性同余方程组,那 exgcd 随便跑。有解情况是 \(b, m\) 互质。这是一个线性同余方程,具体解法下面会提及。
  2. 费马小定理
    只适用于 \(m\) 为质数,由于 \(a^{p - 1}\equiv 1\pmod m\),所以 \(a\times a^{p - 2}\equiv 1 \pmod m\)。所以 \(a^{-1} = a^{p - 2}\)
  3. 线性递推。
    这个就很高级,虽然我觉得它似乎没什么用,因为 OI 里面我们都知道 \(O(n)\) \(O(n\log_2 n)\) 众生平等(划掉
    但是学一手以防万一对吧()
    众所周知,\(1^{-1} = 1\)。我们记 \(ki+r = m\),那么就有
    \(ki+r \equiv 0 \pmod m\)。两边同乘 \(i^{-1}\) 得到
    \(k + ri^{-1}\equiv 0 \pmod m\)\(i^{-1}\equiv -kr^{-1}\pmod m\),即 $ i^{-1}\equiv -\lfloor\dfrac{p}{i}\rfloor (p\bmod i)^{-1}\pmod m$

有了逆元我们就可以做模意义下的除法辣✿✿ヽ(°▽°)ノ✿


7. 线性同余方程

\(ax\equiv b\pmod m\),形如这样的关于 \(x\) 的方程。

脑子告诉我们它等价于这样一个式子 \(ax - km = b\),拿 exgcd 一跑就行了.


8. 线性同余方程组,模数互质(CRT)

这就是我们幼儿园学习过的韩信点兵问题,但是当时没有学一个一般化(雾)的解法。

它是用来解形如 \(\begin{cases}x \equiv r_1 \pmod {m_1} \\ x \equiv r_2\pmod {m_2} \\ \dots \\ x \equiv r_n \pmod {m_n}\end{cases}\)。其中 \(m_1\sim m_n\) 两两互质。

我们记 \(M = \prod\limits_{i = 1}^n m_1,v_i = (\dfrac{M}{m_i})^{-1}(模 m_i 意义下的)\),通解形式是 \(ans = \sum\limits_{i = 1}^n \dfrac{M}{m_i}v_ir_i + kM\),最小解是 \(ans = \sum\limits_{i = 1}^n \dfrac{M}{m_i}v_ir_i \bmod M\)

证明如下:先指针对一个同余方程 \(x\equiv r_i \pmod {m_i}\) 看,计算它的贡献,为了消去 \(x\) 对其它方程组的影响,我们先给它乘上一个 \(\dfrac{M}{m_i}\)。由于我们答案是求和的,这样做它对其它方程组取余的结果就为 \(0\),不会影响答案。

我们令 \(x'\dfrac{M}{m_i}\equiv r_i \pmod {m_i}\),移项得到 \(x' \equiv \dfrac{r_im_i}{M}\pmod {m_i}\),也就是 \(x' \equiv r_i\times (\dfrac{M}{m_i})^{-1}\pmod {m_i}\),这里对答案的贡献就是 \(\dfrac{M}{m_i}v_ir_i\)

CRT 这样的“乘一个倍数消去贡献”的方法很好用,很多题都能用的上,同时对于许多模数有严格限制(比如 NTT)这样的算法,我们可以先拿两个大质数算出解,构造两个同余方程组,然后对于新模数再计算,这样常数固然会比较大,但是相对于 MTT(显而易见我没学过它)好理解十倍甚至九倍(划掉

逆元拿 exgcd 算,代码都是老早之前写的,明天重写一份贴上来 qwq