数论，但是板子 - OIer_SIXIANG

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

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

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

gcd(m,n)={nm=0gcd(n,mmodn)(m≠0)

扩欧可以用来求这个：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+(amodb)y=gcd(a,b)，从这一步再求 ax′+by′=gcd(a,b) 的解（相当于递归回来做），amodb=a−⌊ab⌋b，所以就有
bx+(amodb)y=bx+(a−⌊ab⌋b)y=ay+b(x−⌊ab⌋y)，也就是说 x′=y,y′=x−⌊ab⌋y。

这个玩意儿叫 exgcd

---

2. 二元一次方程的通解

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

首先用 exgcd 求出 ax′+by′=d 的一对解 x′,y′，然后容易得到原方程 ax+by=c 的通解形式是 {x=x′cd+kbdy=y′cd−kad。记 cd=g，那么 {x=x′g+kbdy=y′g−kad 这样写就好看很多了（雾）

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

Task1 正整数解数量

就是求 {x′g+kbd≥1y′g−kad≥1 这个不等式组的整数解数量。不难解出来是 (1−xg)db≤k≤(yg−1)da。由于是整数，所以左边套上向上取整，右边套上向下取整，就得到了 ⌈(1−xg)db⌉≤k≤⌊(yg−1)da⌋。知道取值范围这个就好做了！

Task2 求最大最小解

不难想到 x 越大 y 越小，反之亦然，所以 k=⌈(1−xg)db⌉ 时 x 最小 y 最大，k=⌊(yg−1)da⌋ 时 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≡b(modm)，它们表示 a 与 b 除以 m 的余数相同，炒个例子，6 与 1 关于 5 同余，就可以写成 6≡1(mod5)。

如果 a≡b(modm)，那么 (a+c)≡(b+c)(modm)ac≡bc(modm)ac≡bc(modm)(c|a,c|b)。

同余有如下性质：(a+b)≡(amodm+bmodm)(modm)(a−b)≡(amodm−bmodm)(modm)(a×b)≡(amodm×bmodm)(modm)

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

剩余系：模 n 的完全剩余系是一个集合 Zn，这个集合是 Zn={0,1,2,3,…,n−1}。这里面的元素不是普通的元素，这里面的每个数代表所有与它同余的整数。举个例子，Z7，这里面的 6 元素代表的是 6,13,20…。

简化剩余系（也叫缩系）：将 Zn 里面只保留与 n 互质的数，记为 Z′n（可能不是很规范 qwq）比如 Z′8={1,3,5,7}

由于它们两个非常的与众不同，所以它们的运算也很与众不同，比如 Z5 中 3+4=2((3+4)≡2(mod5)),3×5=0((3∗5)≡0(mod5))。

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

---

4. 欧拉函数的定义

先写一个定义 qwq

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

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

我们记 n 的质因数分别为 p1,p2,…,pk，φ(n)=n(1−1p1)(1−1p2)…(1−1pk)。

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

这样就可以在 O(√n) 的时间复杂度内求出单个 φ(n)

---

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

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

先介绍欧拉定理：aφ(m)≡1(modm)，其中 a,m 互质。

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

证明：对于 m 的简化剩余系 Z′n={x1,x2,…,xφ(m)}，每个元素同乘一个 a 得到 aZ′n={ax1,ax2,…,axφ(m)}。

由于 a 与 m 互质，所以从简化剩余系的角度来看，这两个集合是等价的，所以我们容易得到 φ(m)∏i=1xi≡φ(m)∏i=1axi(modm)，也就是 φ(m)∏i=1xi≡φ(m)∏i=1xiaφ(m)(modm)，所以 aφ(m)≡1(modm)。

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

费马小定理：ap−1≡1(modp)，p 是质数。

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

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

---

有的时候我们需要求 abmodm 的结果，这个时候就不能用常规的方法做了。

逆元可以做这个东西，找到一个 x，使得 ab≡x(modm)。

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

其实，我们只需要求出一个 1b≡x(modm) 的 x，那么 ab 就是两边同乘 a 的结果，这个 x 就叫做 b 在模 m 意义下的逆元，记作 b−1。a/b 就是 a×b−1。

它怎么求？

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

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

---

7. 线性同余方程

ax≡b(modm)，形如这样的关于 x 的方程。

脑子告诉我们它等价于这样一个式子 ax−km=b，拿 exgcd 一跑就行了.

---

8. 线性同余方程组，模数互质（CRT）

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

它是用来解形如 {x≡r1(modm1)x≡r2(modm2)…x≡rn(modmn)。其中 m1∼mn 两两互质。

我们记 M=n∏i=1m1，vi=(Mmi)−1(模mi意义下的)，通解形式是 ans=n∑i=1Mmiviri+kM，最小解是 ans=n∑i=1MmivirimodM。

证明如下：先指针对一个同余方程 x≡ri(modmi) 看，计算它的贡献，为了消去 x 对其它方程组的影响，我们先给它乘上一个 Mmi。由于我们答案是求和的，这样做它对其它方程组取余的结果就为 0，不会影响答案。

我们令 x′Mmi≡ri(modmi)，移项得到 x′≡rimiM(modmi)，也就是 x′≡ri×(Mmi)−1(modmi)，这里对答案的贡献就是 Mmiviri。

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

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