你猜为什么我数学那么差？
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+ (abmod b)y = gcd(a, b))，从这一步再求 (ax'+by' = gcd(a, b)) 的解（相当于递归回来做），(abmod b = a - lfloordfrac{a}{b}rfloor b)，所以就有
(bx+(abmod b)y = bx+(a - lfloordfrac{a}{b}rfloor b)y = ay + b(x - lfloordfrac{a}{b}rfloor y))，也就是说 (x' = y, y' = x - lfloordfrac{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}+kdfrac{b}{d}\ y = y'dfrac{c}{d} - kdfrac{a}{d} end{cases})。记 (dfrac{c}{d} = g)，那么 (begin{cases}x = x'g+kdfrac{b}{d}\ y = y'g-kdfrac{a}{d}end{cases}) 这样写就好看很多了（雾）
下面让我们来做这道题吧。
Task1 正整数解数量
就是求 (begin{cases}x'g+kdfrac{b}{d}ge 1 \ y'g - kdfrac{a}{d} ge 1end{cases}) 这个不等式组的整数解数量。不难解出来是 (dfrac{(1-xg)d}{b}le k le dfrac{(yg - 1)d}{a})。由于是整数，所以左边套上向上取整，右边套上向下取整，就得到了 (lceildfrac{(1-xg)d}{b}rceille k le lfloordfrac{(yg - 1)d}{a}rfloor)。知道取值范围这个就好做了！
Task2 求最大最小解
不难想到 (x) 越大 (y) 越小，反之亦然，所以 (k = lceildfrac{(1-xg)d}{b}rceil) 时 (x) 最小 (y) 最大，(k = lfloordfrac{(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. 同余与一些关于它的定义
同余就是 (aequiv bpmod m)，它们表示 (a) 与 (b) 除以 (m) 的余数相同，炒个例子，(6) 与 (1) 关于 (5) 同余，就可以写成 (6equiv 1 pmod 5)。
如果 (aequiv b pmod m)，那么 ((a+c)equiv (b+c)pmod m\ acequiv bcpmod m \ dfrac{a}{c}equiv dfrac{b}{c}pmod m(c|a, c|b))。
同余有如下性质：((a+b)equiv (abmod m+bbmod m)pmod m\(a-b)equiv (abmod m - bbmod m)pmod m\(atimes b)equiv (abmod 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, 20dots)。
简化剩余系（也叫缩系）：将 (Z_n) 里面只保留与 (n) 互质的数，记为 (Z_n')（可能不是很规范 qwq）比如 (Z_8' = {1, 3, 5, 7})
由于它们两个非常的与众不同，所以它们的运算也很与众不同，比如 (Z_5) 中 (3+4 = 2((3+4)equiv 2 pmod 5), 3times 5 = 0((3*5)equiv 0 pmod 5))。
特别的，在简化剩余系里面乘法封闭，意思就是说这里面做乘法的结果还在原来的集合里面，比如 (Z_8') 里面 (3times 5 = 7) 本来就在里面。这个很好证明，如果 (a) 与 (n) 互质，(b) 与 (n) 互质，那么 (ab) 与 (n) 互质。(gcd(ab, n) = 1)，根据欧几里得算法所以也有 (gcd(ab, n) = gcd(n, abbmod n) = 1)。
4. 欧拉函数的定义
先写一个定义 qwq
请不要认为懂了欧拉函数的定义就啥都明白了，欧拉函数的精髓并不在于它的定义和公式，这里提及完全是为了证欧拉定理费马小定理算逆元（
欧拉函数 (varphi(n)) 定义为 (1sim 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 1pmod 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) 互质，所以从简化剩余系的角度来看，这两个集合是等价的，所以我们容易得到 (prodlimits_{i = 1}^{varphi(m)}x_i equiv prodlimits_{i = 1}^{varphi(m)}ax_ipmod m)，也就是 (prodlimits_{i = 1}^{varphi(m)}x_i equiv prodlimits_{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 xpmod m)。
顺带提一嘴，这里的 (a, b) 都是剩余系意义下的，比如说 (dfrac{3}{7} bmod 5)，你会说诶诶诶这压根不是整数它怎么取余再这样下去得输越南，但是实际上这里的 (3) 是一个除以 (5) 余 (3) 的数，(7) 同理，这个时候就能整除了。
其实，我们只需要求出一个 (dfrac{1}{b} equiv xpmod m) 的 (x)，那么 (dfrac{a}{b}) 就是两边同乘 (a) 的结果，这个 (x) 就叫做 (b) 在模 (m) 意义下的逆元，记作 (b^{-1})。(a / b) 就是 (atimes b^{-1})。
它怎么求？
- exgcd
转化一下 (xbequiv 1 pmod m)，线性同余方程组，那 exgcd 随便跑。有解情况是 (b, m) 互质。这是一个线性同余方程，具体解法下面会提及。 - 费马小定理
只适用于 (m) 为质数，由于 (a^{p - 1}equiv 1pmod m)，所以 (atimes a^{p - 2}equiv 1 pmod m)。所以 (a^{-1} = a^{p - 2})。 - 线性递推。
这个就很高级，虽然我觉得它似乎没什么用，因为 OI 里面我们都知道 (O(n)) (O(nlog_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 -lfloordfrac{p}{i}rfloor (pbmod i)^{-1}pmod m$
有了逆元我们就可以做模意义下的除法辣✿✿ヽ(°▽°)ノ✿
7. 线性同余方程
(axequiv bpmod m)，形如这样的关于 (x) 的方程。
脑子告诉我们它等价于这样一个式子 (ax - km = b)，拿 exgcd 一跑就行了.
8. 线性同余方程组，模数互质（CRT）
这就是我们幼儿园学习过的韩信点兵问题，但是当时没有学一个一般化（雾）的解法。
它是用来解形如 (begin{cases}x equiv r_1 pmod {m_1} \ x equiv r_2pmod {m_2} \ dots \ x equiv r_n pmod {m_n}end{cases})。其中 (m_1sim m_n) 两两互质。
我们记 (M = prodlimits_{i = 1}^n m_1，v_i = (dfrac{M}{m_i})^{-1}(模 m_i 意义下的))，通解形式是 (ans = sumlimits_{i = 1}^n dfrac{M}{m_i}v_ir_i + kM)，最小解是 (ans = sumlimits_{i = 1}^n dfrac{M}{m_i}v_ir_i bmod M)。
证明如下：先指针对一个同余方程 (xequiv 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_itimes (dfrac{M}{m_i})^{-1}pmod {m_i})，这里对答案的贡献就是 (dfrac{M}{m_i}v_ir_i)。
CRT 这样的“乘一个倍数消去贡献”的方法很好用，很多题都能用的上，同时对于许多模数有严格限制（比如 NTT）这样的算法，我们可以先拿两个大质数算出解，构造个同余方程组，然后对于新模数再计算，这样常数固然会比较大，但是相对于 MTT（显而易见我没学过它）好理解十倍甚至九倍（划掉
逆元拿 exgcd 算，代码都是老早之前写的，明天重写一份贴上来 qwq
9. 线性同余方程组，模数不一定互质（exCRT）
它还是用来解 (begin{cases}x equiv r_1 pmod {m_1} \ x equiv r_2pmod {m_2} \ dots \ x equiv r_n pmod {m_n}end{cases}) 这样的同余方程组，但不同的是这时候 (m_1, m_2, dots, m_n) 不一定两两互质。
exCRT 其实和 CRT 真的什么关系都没有了，它的思想是合并同余方程。假设我们已经求出来前 (k - 1) 个方程的一个解 (x')，下面我们希望 (x) 能够写成 (x' + a) 的形式，使得 (x equiv r_k pmod {m_k})。
和 CRT 一样，为了不让我们加上的数字对前面的方程产生影响，我们选择加上一个 (operatorname{lcm}(m_1, m_2, m_3, dots, m_{k - 1})) 的倍数，记 (M = operatorname{lcm}(m_1, m_2, m_3, dots, m_{k - 1}))，那么我们就可以把我们要构造出来的 (x) 写成 (x'+tM) 的形式。此时 (x'+tMequiv r_kpmod {m_{k}})。移项得到 (tM equiv r_k - x'pmod {m_k})。用 exgcd 解出来这个线性同余方程，我们就可以得到一个 (t)，最后 (x = x' + tM)。
根据数学归纳法，发现了没有：我们解出来了！
代码也明天填坑 qwq
下面会把 bsgs，exbsgs，欧拉函数性质和求法，积性函数有关的狄利克雷卷积和莫反补上去。
还有一些其它的 Lucas 和扩展欧拉定理……Lucas 曾经会证（现在不会了），扩展欧拉定理一直不会证，不过这两个不好在上面做什么变形就直接拍上去就好了（划掉
（就是菜
写这篇文章可以看做是梳理一下我学过的幼儿园数论知识们，也方便我复习之类的 qwq。听说还有什么 Min25 筛鸭，洲阁筛鸭这些很高级的东西，但是我是幼儿园小朋友，所以暂时用不到那么高级的东西。
