我也不知道这是从哪本书上抠来的？

整除

定义 1：如果 $a$ 和 $b$ 为整数且 $a \ne 0$，我们说 $a$ 整除 $b$ 是指存在整数 $c$ 使得 $b=ac$。如果 $a$ 整除 $b$，我们还称 $a$ 是 $b$ 的一个因子，且称 $b$ 是 $a$ 的倍数。

如果 $a$ 整除 $b$，则将其记为 $a \mid b$，如果 $a$ 不能整除 $b$，则记其为 $a \nmid b$。

定理 1：如果 $a, b$ 和 $c$ 是整数，且 $a \mid b, b \mid c$，则 $a \mid c$。

定理 2：如果 $a, b, m$ 和 $n$ 为整数，且 $c \mid a, c \mid b$，则 $c \mid (ma+nb)$。

定理 3：带余除法 如果 $a$ 和 $b$ 是整数且 $b \gt 0$，则存在唯一的整数 $q$ 和 $r$，使得$a = bq + r, 0 ≤ r < b$。

最大公因子及其性质

定义 2：不全为零的整数 $a$ 和 $b$ 的最大公因子是指能够同时整除 $a$ 和 $b$ 的最大整数。

定义 3：设 $a,b$ 均为非零整数，如果 $a$ 和 $b$ 最大公因子 $(a,b)=1$，则称 $a$ 与 $b$ 互素。

定理 4：$a，b$ 是整数，且 $(a, b)=d$，那么 $(a/d, b/d)=1$。（换言之，$a/d$ 与 $b/d$ 互素）

推论 1：如果 $a, b$ 为整数，且 $b\ne 0$，则 $a/b=p/q$，其中 $p, q$ 为整数，且 $(p,q)=1, q≠0$。

定理 5：令 $a, b, c$ 是整数，那么 $(a+cb, b) = (a, b)$

证明：令 $a, b, c$ 是整数，证明 $a, b$ 的公因子与 $a+cb, b$ 的公因子相同，即证明 $(a+cb, b)=(a, b)$。

令 $e$ 是 $a, b$ 的公因子，由定理 2 可知 $e \mid (a+cb)$，所以 $e$ 是 $a+cb$ 和 $b$ 的公因子。

如果 $f$ 是 $a+cb$ 和 $b$ 的公因子，由定理 2 可知 $f$ 整除 $(a+cb)-cb=a$，所以 $f$ 是 $a, b$ 的公因子，因此 $(a+cb, b)=(a,b)$。

定义 4：线性组合 如果 $a,b$ 是整数，那么它们的线性组合具有形式 $ma+nb$，其中 $m,n$ 都是整数。

定理 6：两个不全为零的整数 $a, b$ 的最大公因子是 $a, b$ 的线性组合中最小的正整数。

证明：令 $d$ 是 $a,b$ 的线性组合中最小的正整数，$d = ma + nb$，其中 $m,n$ 是整数，我们将证明 $d\mid a, d\mid b$。

由带余除法，得到 $a=dq+r, 0\le r\lt d$。

由 $a=dq+r $和 $d=ma+nb$，得到 $r=a-dq=a-q(ma+nb)=(1-qm)a-qnb$。

这就证明了整数 $r$ 是 $a,b$ 的线性组合。因为 $0 \le r \lt d$，而 $d$ 是 $a,b$ 的线性组合中最小的正整数，

于是我们得到 $r=0$（如果 $r$ 不是等于 $0$，那意味着 $r$ 才是所有线性组合中最小的正整数，这与 $d$ 是所有线性组合中最小的正整数矛盾），因此 $d\mid a$，同理可得，$d\mid b$。

我们证明了 $a,b$ 的线性组合中最小的正整数 $d$ 是 $a,b$ 的公因子，剩下要证的是它是 $a,b$ 的最大公因子，为此只需证明 $a,b$ 所有的公因子都能整除 $d$。

由于 $d = ma + nb$，因此如果 $c \mid a$ 且 $c \mid b$，那么由定理 2 有 $c \mid d$，因此 $d \gt c$，这就完成了证明。

定义 5：令 $a_1,a_2,…,a_n$ 是不全为零的整数，这些整数的公因子中最大的整数就是最大公因子。$a_1,a_2,…,a_n$ 的最大公因子记为 $(a_1, a_2, …, a_n)$。

引理 1：如果 $a_1,a_2,…,a_n$ 是不全为零的整数，那么 $(a_1, a_2, …, a_{n-1}, a_n) = (a_1, a_2, …, (a_{n-1}, a_n))$。

欧几里得算法

辗转相除法求 gcd，即 $\gcd(a, b) = \gcd(b, a\bmod b)$。

证明 1：由定理 3 带余除法，存在整数 $q, r$ 使得 $a = bq + r, 0 \le r \lt b$, 得到 $r = a - bq$。由定理 5 得，$\gcd(a,b) = \gcd(a-bq,b) = \gcd(r,b) = \gcd(a%b,b) = \gcd(b,a%b)$。

证明 2：令 $d=(a,b)$，证明 $d \mid (b,a\bmod b)$，再反证 $(b,a\bmod b) \gt d$ 是不可能的。

时间复杂度的证明：

假设 $a\gt b$，分两种情况：

1. $b \lt a/2$， 经过一次辗转得到 $(b,a\bmod b)$，$\max(a,b)$ 至少缩小一半。
2. $b \ge a/2$，经过两次辗转得到彼时的 $\max(a,b)$ 至少缩小一半。

综上所述，最多 $2\log(n)$ 次辗转算法结束。

裴蜀定理

如果 $a$ 与 $b$ 均为整数，则存在整数 $x$ 和 $y$ 满足 $ax + by = (a,b)$。

由定理 6 容易证明正确性。

下面用扩展欧几里得算法（exgcd）求出满足 $ax + by = (a,b)$ 的一个特解。

例如：$a = 99, b = 78$， 令 $d =(a,b) = (99,78) = 3$，求 $99x + 78y = 3$ 的一个特解。

在调用 exgcd 的时候，从后往前依次构造出相应的解。

在用欧几里得算法求 $(99,78)$ 的时候，是要先求 $(78,21)$。

假如已经求出 $78x + 21y = 3$ 的一个解 ${x_0,y_0} = {3,-11}$，即 $78x_0 + 21y_0 = 3$。

那么可以由 $78x_0 + 21y_0 = 3$，构造出 $99x + 78y = 3$ 的一个特解。

因 $a=99, b=78, a\bmod b=21$, 因此 $78x_0 + 21y_0 = 3$，可以写成：$bx_0 + (a\bmod b)y_0 = 3$，即 $bx_0+(a-\frac{a}{b}b)y_0=3$，即 $ay_0+b(x_0-\frac{a}{b}y_0)=3$，即 $99y_0+78(x_0-\frac{99}{78}y_0)=3$。

那么只需要令 $x = y_0 = -11, y = x_0 - \frac{99}{78}y_0=14$，就可以得到 $99x + 78y = 3$ 的一个特解，即 ${-11, 14}$ 是 $99x+78y=3$ 的一个特解。

也就是说，在用欧几里得算法求 $(78,21)$ 的时候，若能返回 ${x_0,y_0}$ 使得满足 $78x_0 + 21y_0 = 3$，那么就能构造出一个特解 ${x,y}$ 满足 $99x + 78y = 3$ 的一个特解。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void exgcd(int a, int b, int &d, int &x, int &y) {
 if (!b) {
 d = a;
 x = 1;
 y = 0;
 return;
 }
 exgcd(b, a % b, d, x, y);
 int t = x;
 x = y;
 y = t - (a / b) * y;
 return;
}

注意：若 $a\lt 0$ 且 $b\ge 0$ 那么在求 $ax+by=(a,b)$ 的时候，可以先求出 $|a|x+by=(|a|,b)$ 的一组解 ${x_0,y_0}$，然后 ${-x_0,y_0}$ 就是原方程的一个解。

若 $a\ge 0$ 且 $b\lt 0$ 的同理。若 $a \lt 0$ 且 $b \lt 0$ 的也同理。

定理 7：如果 $a,b$ 是正整数，那么所有 $a,b$ 的线性组合构成的集合与所有 $(a,b)$ 的倍数构成的集合相同。

证明：假设 $d = (a,b)$。

1. 首先证明每个 $a,b$ 的线性组合是 $d$ 的倍数。首先注意到由最大公因子的定义，有 $d\mid a$ 且 $d\mid b$，每个 $a,b$ 的线性组合具有形式 $ma+nb$，其中 $m,n$ 是整数。

由定理 2，只要 $m,n$ 是整数，$d$ 就整除 $ma+nb$，因此，$ma+nb$ 是 $d$ 的倍数。

2. 现在证明每一个 $d$ 的倍数也是 $(a，b)$ 的线性组合。

由定理 6，存在整数 $r,s$ 使得 $(a,b) = ra + sb$。而 $d$ 的倍数具有形式 $jd$，其中 $j$ 是整数。

在方程 $d = ra + sb$ 的两边同时乘以 $j$，我们得到 $jd = (jr)a + (js)b$。

因此，每个 $d$ 的倍数是 $(a,b)$ 的线性组合。

推论 2：整数 $a$ 与 $b$ 互素当且仅当存在整数 $m$ 和 $n$ 使得 $ma + nb = 1$。

证明：如果 $a，b$ 互素，那么 $(a,b)=1$，由定理 6 可知，$1$ 是 $a$ 和 $b$ 的线性组合的最小正整数，于是存在整数 $m,n$ 使得 $ma + nb = 1$。

反之，如果有整数 $m$ 和 $n$ 使得 $ma + nb = 1$，则由定理 6 可得 $(a,b)=1$，这是由于 $a,b$ 不同为 $0$ 且 $1$ 显然是 $a,b$ 的线性组合中的最小正整数。

二元一次不定方程

引理 2：如果 $a, b, c$ 是正整数，满足 $(a, b) = 1, a \mid bc$，则 $a \mid c$。

证明：由于 $(a, b)=1$，存在整数 $x$ 和 $y$ 使得 $ax+by=1$。等式两边同时乘以$c$，得 $acx+bcy=c$。

根据定理 2，$a$ 整除 $(cx)a + y(bc)$，这是因为这是 $a$ 和 $bc$ 的线性组合，而它们都可以被 $a$ 整除。因此，$a \mid c$。

定理 8：设 $a,b$ 是整数且 $d=(a,b)$。如果 $d \nmid c$，那么方程 $ax+by=c$ 没有整数解，如果 $d \mid c$，那么存在无穷多个整数解。

另外，如果 $x = x_0, y = y_0$ 是方程的一个特解，那么所有的解可以表示为：$x = x_0 + (b/d)n， y = y_0 - (a/d)n$，其中 $n$ 是整数。

证明：由定理 7 可知，$ax+by$ 的结果是 $d$ 的倍数，因此如果 $d \nmid c$，那么方程 $ax+by=c$ 没有整数解。

如果 $d\mid c$，存在整数 $s, t$ 使得 $as+bt=d$。

因为 $d\mid c$，存在整数 $e$ 使得 $de = c, c = de = (as+bt)e = a(se)+b(te)$

因此 $x_0 = se, y_0 = te$ 是方程 $ax + by = c$ 的一个特解。

为了证明方程存在无穷多个解，令 $x = x_0 + (b/d)n, y = y_0 - (a/d)n$，其中 $n$ 是整数。

1. 证明任何一对整数 $(x_0+(b/d)n, y_0 - (a/d)n)$ 它是方程的解。

因为 $a(x_0+(b/d)n) + b(y_0 - (a/d)n) = ax_0 + by_0 + a(b/d)n - b(a/d)n = ax_0 + by_0$，而 $ax_0+by_0$ 是方程 $ax+by=c$ 的解，所以 $(x_0+(b/d)n, y_0 -(a/d)n)$ 就是方程的解。

2. 证明方程的任何一个解都具有 $(x_0 + (b/d)n, y_0 - (a/d)n)$ 这种形式。

假设整数 $x,y$ 满足 $ax+by=c$，又因为 $ax_0+by_0=c$，两式相减得到：$a(x-x_0)+b(y-y_0)=0$。

即 $a(x-x_0) = b(y_0-y)$，等式两边同时除以 $d$ 得到 $(a/d)(x-x_0) = (b/d)(y_0-y)$，根据定理 4，$a/d$ 与 $b/d$ 互质，再根据引理 2，$(a/d) \mid (y_0-y)$，因此存在整数 $n$ 使得 $(a/d)n = y_0 - y$，于是得到 $y=y_0-(a/d)n$。

同理可得，$(b/d) \mid (x-x_0)$，因此存在整数 $n$ 使得 $(b/d)n = x - x_0$，于是得到 $x=x_0+(b/d)n$。

习题

1. Luogu-P5656 【模板】二元一次不定方程 (exgcd) Orz 离散小波变换°

下面设 $p = b/d, q = a/d$。

有正整数解：

• 解的个数：不断地将 $y_0$ 减去 $q$，$x_0$ 加上 $p$ 就可以找到所有可行解，个数为 $\lfloor (y-1)/q\rfloor + 1$
• $x$ 的最小正整数值：exgcd 得到的 $x_0$
• $y$ 的最小正整数值：不断地将 $y_0$ 减去 $q$（因为 $x_0$ 最小时，$y_0$ 一定最大），答案为 $(y-1)\bmod q+1$（特别注意 $0$ 的情况）
• $x$ 的最大正整数值：不断将 $x_0$ 加上 $p$，答案为 $x+\lfloor (y-1)/q\rfloor * p$
• $y$ 的最大正整数值：$x_0$ 为最小正整数时，$y_0$ 就是最大值

无正整数解：

• $x$ 的最小正整数值：exgcd 得到的 $x_0$
• $y$ 的最小正整数值：当前的 $y_0 \le 0$，需要执行构造 $x_0$ 的方法，即 $y_0 + q * \lceil (1.0-y)/q \rceil$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <bits/stdc++.h>
using namespace std;
#define LL long long
void exgcd(LL a, LL b, LL &d, LL &x, LL &y) {
 if (b == 0) {
 d = a;
 x = 1;
 y = 0;
 return;
 }
 exgcd(b, a%b, d, x, y);
 LL t = x;
 x = y;
 y = t-(a/b)*y;
}
int main()
{
 int t;
 cin >> t;
 while (t--) {
 LL a, b, c, x, y, d;
 cin >> a >> b >> c;
 exgcd(a, b, d, x, y);
 if (c%d != 0) {
 puts("-1");
 } else {
 x *= c/d;
 y *= c/d;
 LL p = b/d, q = a/d, k;
 if (x < 0) { k = ceil((1.0-x)/p); x += p*k; y -= q*k; }
 if (x >= 0) { k = (x-1)/p; x -= p*k; y += q*k; }
 if (y > 0) {
 cout << (y-1)/q+1 << " " << x << " " << (y-1)%q+1 << " " << x+(y-1)/q*p << " " << y << endl;
 } else {
 cout << x << " " << y+q*(LL)ceil((1.0-y)/q) << endl;
 }
 }
 }
 return 0;
}

2. 多元一次不定方程的一组解：求 $a_1x_1 + a_2x_2 + a_3x_3 + … + a_nx_n = c$ 的一组整数解，如无整数解输出 $-1$。

先考虑三元一次不定方程 $a_1x_1 + a_2x_2 + a_3+x_3 = c$。可以用 exgcd 解二元一次方程 $a_1x_1 + a_2x_2 = (a_1, a_2)$，设 $d = (a_1, a_2)$，由定理 8 知道 $d$ 乘任何整数时该方程都有整数解，就可以把 $d$ 当做原方程的一个系数，转而求解 $dt+a_3x_3 = c$。上一步的方程变为 $t(a_1x_1 + a_2x_2) = td$，于是将 $t$ 乘上前面的 $x_1, x_2$ 就得到最终答案。

多元同理。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int main()
{
 exgcd(a[1], a[2], ta[2], ans[1], ans[2]);
 int tm = 1;
 for (int i = 3; i <= n; i++) {
 LL tmp;
 exgcd(ta[i-1], a[i], ta[i], tmp, ans[i]);
 if (i == n && c%ta[i]) { cout << -1 << endl; return 0; }
 for (int j = 1; j < i; j++) ans[j] *= tmp;
 }
 tm = c/ta[n];
 for (int i = 1; i <= n; i++) {
 cout << ans[i]*tm <<" ";
 }
 return 0;
}

3. Luogu-P3986 斐波那契数列：求 $f(i)x+f(i+1)y=k$ 的正整数解个数（$f$ 表示斐波那契数列）

显然 $f(i)+f(i+1)\gt k$ 时就不用继续下去了，因此方程的个数是有限的，可以枚举。

然后题目就变成了求 $f_ia+f_{i+1}b=k$ 的正整数解的个数。

另外，有没有可能同样的 $(a, b)$ 出现了两次呢？不可能。否则就需要满足 $af_i+bf_{i+1}=af_j+bf_{j+1}, i \ne j$，然而斐波那契数列任两项不相等，以上式子不成立。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int main()
{
 LL n;
 cin >> n;
 fib[0] = fib[1] = 1;
 for (int i = 2; i <= 50; i++) fib[i] = fib[i-1]+fib[i-2];
 LL ans = 0;
 for (int i = 1; fib[i] < n; i++) {
 LL d, x, y, k;
 exgcd(fib[i-1], fib[i], d, x, y);
 LL p = fib[i]/d, q = fib[i-1]/d;
 x = x*(n/d), y = y*(n/d);
 if (x <= 0) {
 k = ceil((1.0-x)/p);
 x += k*p;
 y -= k*q;
 }
 if (x >= 0) {
 k = (x-1)/p;
 x -= k*p;
 y += k*q;
 }
 if (x <= 0 || y <= 0) continue;
 ans = ((y-1)/q+1+ans)%MOD;
 }
 cout << ans << endl;
 return 0;
}

同余

同余概述

定义 6：设 $m$ 是正整数，若 $a$ 和 $b$ 是整数，且 $m\mid (a-b)$，则称 $a$ 和 $b$ 模 $m$ 同余。

若 $a$ 和 $b$ 模 $m$ 同余，则记 $a\equiv b(mod\ m)$。

若 $m \nmid (a-b)$，则记 $a\not\equiv b (mod\ m)$，并称 $a$ 模 $m$ 不同余于 $b$。

整数 $m$ 称为同余的模。

定理 9：若 $a$ 和 $b$ 是整数，则 $a\equiv b(mod\ m)$ 当且仅当存在整数 $k$，使得 $a=b+km$。

证明：若 $a\equiv b(mod\ m)$，则 $m\mid (a-b)$，这说明存在整数 $k$，使得 $km=a-b$，所以 $a=b+km$。

反过来，若存在整数 $k$ 使得 $a=b+km$，则 $km=a-b$。于是，$m\mid (a-b)$，因而 $a\equiv b(mod\ m)$。

例：$19\equiv -2(mod\ 7)$ 和 $19=-2+3·7$。

定理 10：设 $m$ 是正整数，模 $m$ 的同余满足下面的性质:

1. 自反性。若 $a$ 是整数，则 $a\equiv a(mod\ m)$。
2. 对称性。若 $a$ 和 $b$ 是整数，且 $a\equiv b(mod\ m)$，则 $b\equiv a(mod\ m)$。
3. 传递性。若 $a,b,c$ 是整数，且 $a\equiv b(mod\ m)$ 和 $b\equiv c(mod\ m)$，则 $a\equiv c(mod\ m)$。

证明：

1. 因为 $m\mid(a-a)=0$，所以 $a=a(mod\ m)$。
2. 若 $a\equiv b(mod\ m)$，则 $m\mid(a-b)$。从而存在整数 $k$，使得 $km=a-b$。这说明 $(-k)m=b-a$，即 $m\mid (b-a)$。因此，$b\equiv a(mod\ m)$。
3. 若 $a\equiv b(mod\ m)$，且 $b\equiv c(mod\ m)$，则有 $m\mid (a-b)$ 和 $m\mid (b-c)$。从而存在整数 $k$ 和 $l$，使得 $km=a-b,lm=b-c$。于是，$a-c=(a-b)+(b-c)=km+lm=(k+l)m$。因此，$m\mid(a-c), a\equiv c(mod\ m)$。

由定理 10 可见，整数的集合被分成 $m$ 个不同的集合，这些集合称为模 $m$ 剩余类（同余类），每个同余类中的任意两个整数都是模 $m$ 同余的。

注意，当 $m=2$ 时，正好整数分成奇、偶两类.

如果你对集合上的关系比较熟悉，那么定理 10 表明对正整数 $m$ 的模 $m$ 同余是一种等价关系，并且每一个模 $m$ 同余类即是由此种等价关系所定义的等价类。

例模 $4$ 的四个同余类是：

$$ …\equiv 8\equiv -4\equiv 0\equiv 4\equiv 8\equiv …(mod\ 4) \\ …\equiv -7\equiv -3\equiv 1\equiv 5\equiv 9\equiv …(mod\ 4) \\ …\equiv -6\equiv -2\equiv 2\equiv 6\equiv 10\equiv …(mod\ 4) \\ …\equiv -5\equiv -1\equiv 3\equiv 7\equiv 11\equiv …(mod\ 4) \\ $$

设 $m$ 是正整数，给定整数 $a$，由带余除法有 $a = bm + r$，其中 $0\le r \lt m-1$，称 $r$ 为 $a$ 的模 $m$ 最小非负剩余，是 $a$ 模 $m$ 的结果，类似地，当 $m$ 不整除 $a$ 时，称 $r$ 为 $a$ 的模 $m$ 最小正剩余。

$mod\ m$ 实际上是从整数集到集合 ${0,1,2,…,m-1}$ 的函数。

定理 11：若 $a$ 与 $b$ 为整数，$m$ 为正整数，则 $a\equiv b(mod\ m)$ 当且仅当 $a \bmod m = b \bmod m$。

证明：

1. 若 $a\equiv b(mod\ m)$ 则 $a\bmod m = b \bmod m$。

由带余除法 $a=pm+ra , b=qm+rb$，因 $a\equiv b(mod\ m)$，则 $m\mid a-b$，则 $m\mid (p-q)m+(ra-rb)$，则存在整数 $x$，满足 $xm = (p-q)m+(ra-rb)$，则 $ra-rb = (x-p+q)m$，则 $ra-rb\mid m$。

因 $0\le ra\lt m, 0\le rb\lt m$, 故 $-(m-1) \le ra-rb \lt m$，故 $ra-rb$ 只能是 $0$ 才能满足 $ra-rb\mid m$。

则 $ra = rb$，则 $ra=a \bmod m, rb=b \bmod m$，则 $a \bmod m = b \bmod m$。

2. 若 $a \bmod m = b \bmod m$ 则 $a\equiv b(mod\ m)$。

由带余除法 $a=pm+ra , b=qm+rb$，若 $a \bmod m = b \bmod m$，则 $ra=rb$。

因此 $a-b = (pm+ra)-(qm+rb)=(p-q)m + (ra-rb) = (p-q)m$。因此 $m\mid a-b$，故 $a\equiv b(mod\ m)$。

因此，每个整数都和 $0,1,…,m-1$（也就是 $a$ 被 $m$ 除所得的余数）中的一个模 $m$ 同余。因为 $0,1,…,m-1$ 中的任何两个都不是模 $m$ 同余的，所以有 $m$ 个整数使得每个整数都恰与这 $m$ 个整数中的一个同余。

定理 12：若 $a,b,c,m$ 是整数，$m\gt 0$，且 $a\equiv b(mod\ m)$，则

1. $a+c\equiv b+c(mod\ m)$
2. $a-c\equiv b-c(mod\ m)$
3. $ac\equiv bc(mod\ m)$

定理 13：若 $a,b,c,m$ 是整数，$m\gt 0, d=(c,m)$，且有 $ac\equiv bc(mod\ m)$，则 $a\equiv b(mod\ m/d)$。

证明：若 $ac\equiv bc(mod\ m)$，所以存在整数 $k$ 满足 $c(a-b)=km$，两边同时除以 $d$，得到：$(c/d)(a-b)=k(m/d)$，因为 $(m/d,c/d)=1$，根据引理 2，$m/d\mid a-b$，因此 $a\equiv b(mod\ m/d)$。

下面的推论是定理 13 的特殊情形，经常用到，它使得我们能够在模 $m$ 同余式中消去与模 $m$ 互素的数。

推论 3：若 $a,b,c,m$ 是整数，$m\gt 0,(c，m)=1$，且有 $ac\equiv bc(mod\ m)$，则 $a\equiv b(mod\ m)$。

定理 14 ：若 $a,b,c,m$ 是整数，$m\gt 0,a\equiv b(mod\ m)$，且 $c\equiv d(mod\ m)$，则:

1. $a+c\equiv b+d(mod\ m)$
2. $a-c\equiv b-d(mod\ m)$
3. $ac\equiv bd(mod\ m)$

证明：

因为 $a\equiv b(mod\ m)$ 且 $c\equiv d(mod\ m)$，我们有 $m\mid (a-b)$ 与 $m\mid (c-d)$。因此，存在整数 $k$ 与 $l$ 使得 $km=a-b,lm=c-d$。

为证 1，注意到 $(a+c)-(b+d)=(a-b)+(c-d)=km+lm=(k+l)m$.因此 $m\mid (a+c)-(b+d)$，即 $a+c\equiv b+d(mod\ m)$。

为证 2，注意到 $(a-c)-(b-d)=(a-b)-(c-d)=km-lm=(k-1)m$，因此 $m\mid (a-c)-(b-d)$，即 $a-c\equiv b-d(mod\ m)$.

为证 3，注意到 $ac-bd=ac-bd+bc-bd=c(a-b)+b(c-d)=ckm+blm=m(ck+ bl)$。因此，$m\mid ac-bd$，即 $ac\equiv bd(mod\ m)$。

定义 7：一个模 $m$ 完全剩余系是一个整数的集合，使得每个整数恰和此集合中的一个元素模 $m$ 同余。

例如：整数 $0,1,…,m-1$ 的集合是模 $m$ 完全剩余系，称为模 $m$ 最小非负剩余的集合。

下面的引理帮助我们判定一个 $m$ 元集合是否为模 $m$ 的完全剩余系.

引理 3：$m$ 个模 $m$ 不同余的整数的集合构成一个模 $m$ 的完全剩余系。

证明：

假设 $m$ 个模 $m$ 不同余的整数集合不是模 $m$ 完全剩余系，这说明，至少有一个整数 $a$ 不同余于此集合中的任一整数。

所以此集合中的整数都模 $m$ 不同余于 $a$ 被 $m$ 除所得的余数，从而，整数被 $m$ 除得的不同剩余至多有 $m-1$ 个。

由鸽笼原理，此集合中至少有两个整数有相同的模 $m$ 剩余。

这不可能，因为这些整数均模 $m$ 不同余，因此，$m$ 个模 $m$ 不同余的整数的集合构成一个模 $m$ 的完全剩余系。

定理 15：若 $r_1,r_2,…,r_m$ 是一个模 $m$ 的完全剩余系，且正整数 $a$ 满足 $(a,m)=1$，则对任何整数 $b$，$ar_1+b, ar_2+b,…,ar_m+b$ 都是模 $m$ 的完全剩余系。

证明：首先来证整数 $ar_1+b, ar_2+b,…,ar_m+b$ 中的任何两个都模 $m$ 不同余。

反证，若存在 $1\le j,k\le m$ 且 $j\ne k$ 且 $ar_j+b \equiv ar_k+b(mod\ m)$，则由定理 12.2 可知：$ar_j \equiv ar_k(mod\ m)$。因为 $(a，m)=1$，推论 3 表明 $r_j\equiv r_k(mod\ m)$，这与 $r_1,r_2,…,r_m$ 是一个模 $m$ 的完全剩余系相矛盾。

故 $ar_1+b, ar_2+b,…,ar_m+b$ 是 $m$ 个模 $m$​ 不同余的整数，由引理 3，命题得证。

定理 16：若 $a,b,k,m$ 是整数，$k\gt 0,m\gt 0$，且 $a\equiv b(mod\ m)$，则 $a^k\equiv b^k(mod\ m)$。

证明：因为 $a\equiv b(mod\ m)$，所以 $m\mid a-b$。

因为 $a^k-b^k =(a-b)(a^{k-1}+a^{k-2}b+…ab^{k-2}+b^{k-1})$ （可以参考资料：详聊如何理解a^n-b^n因式分解）

所以 $a-b \mid a^k-b^k$，根据 定理 1，$m \mid a^k-b^k$，即 $a^k\equiv b^k(mod\ m)$。

线性同余方程

设 $x$ 是未知整数，形如 $ax\equiv b(mod\ m)$ 的同余式称为一元线性同余方程。

首先注意到，若 $x=x_0$ 是同余方程 $ax\equiv b(mod\ m)$ 的一个解，且 $x_1\equiv x_0(mod\ m)$，则 $ax_1\equiv ax_0 \equiv b(mod\ m)$，所以 $x_1$ 也是一个解。

因此，若一个模 $m$ 同余类的某个元素是解，则此同余类的所有元素都是解。

于是，我们会问模 $m$ 的 $m$ 个同余类中有多少个是给出方程的解，这相当于问方程有多少个模 $m$ 不同余的解。

定理 17：设 $a,b,m$ 是整数，$m\gt 0,(a,m)=d$。

若 $d\nmid b$，则 $ax\equiv b(mod\ m)$ 无解。

若 $d\mid b$，则 $ax\equiv b(mod\ m)$ 恰有 $d$ 个模 $m$ 不同余的解。

证明：根据定理 9，线性同余方程 $ax\equiv b(mod\ m)$ 可以写成二元线性不定方程 $ax+my=b$。其中 $x, y$ 是未知数。整数 $x$ 是 $ax\equiv b(mod\ m)$ 的解当且仅当存在整数 $y$ 使得 $ax+my=b$。

由定理 8 可知，若 $d\nmid b$，则无解，而 $d\mid b$ 时，$ax-my=b$ 有无穷多解：$x = x_0 + (m/d)t, y = y - (a/d)t$，

其中 $x=x_0$ 和 $y=y_0$ 是方程的特解，上述 $x$ 的值 $x=x_0+(m/d)t$ 是线性同余方程的解，有无穷多这样的解。

为确定有多少不同余的解，我们来找两个解 $x_1=x_0+(m/d)t1$ 和 $x_2=x_0+(m/d)t2$ 模 $m$ 同余的条件，若这两个解同余，则 $(x0+(m/d)t1)\equiv (x0+(m/d)t2) (mod\ m)$。

根据 定理 12，两边减去 $x_0$，有 $(m/d)t1\equiv (m/d)t2(mod\ m)$。

因为 $(m/d)\mid m$，所以 $(m,m/d)=m/d$，再由 定理 13 得，$t1\equiv t2 (mod\ d)$。

这表明不同余的解的一个完全集合可以通过取 $x=x_0+(m/d)t$ 得到，其中 $t$ 取遍模 $d$ 的完全剩余系，一个这样的集合可由 $x=x_0+(m/d)t$ 给出，其中 $t=0,1,2,…,d-1$。

推论 4：若 $a$ 和 $m\gt 0$ 互素，且 $b$ 是整数，则线性同余方程 $ax\equiv b(mod\ m)$ 有模 $m$ 的唯一解。

证明：

因为 $(a,m)=1$，所以 $(a,m)\mid b$。因此，由 定理 17，线性同余方程 $ax\equiv b(mod\ m)$ 恰有 $(a,m)=1$ 个模 $m$ 不同余的解。

例：为求出 $9x\equiv 12(mod\ 15)$ 的所有解，首先注意到因为 $(9,15)=3$ 且 $3\mid 12$，所以恰有三个不同余的解，我们可以通过先找到一个特解，再加上 $15/3=5$ 的适当倍数来求得所有的解。

为求特解，我们考虑二元线性不定方程 $9x-15y=12$。由扩展欧几里得算法得到：$9x-15y=12$ 的一个特解是 $x_0=8$ 和 $y_0=4$。

由定理 17 的证明可知，三个不同余的解由 $x= x_0\equiv 8(mod\ 15),x= x_0+5\equiv 13(mod\ 15)$ 和 $x= x_0+5*2\equiv 18\equiv 3(mod\ 15)$ 给出。

习题

Luogu-P1516 青蛙的约会 Orz 题解 P1516 【青蛙的约会】 - FlashHu

如果两蛙相遇，那么他们的初始坐标差 $x-y$ 和跳的距离 $(n-m)t$ 之差应该模纬度线总长 $l$ 同余，$(n-m)t\equiv x-y(mod\ l)$。转化成不定方程的形式：$(n-m)t+kl=x-y$，并求最小正整数解。设 $a=n-m,b=l,c=x-y$，可以写成 $ax+by = c$，通过 exgcd 可以求出 x 的一个特解。

细节问题，因为 gcd 只对非负整数有意义，如果 $a\lt 0$ 时等式两边要同时取负，$a,c$ 变成相反数（相当于把两个蛙交换了一下），$b$ 是正数所以不能变。

这里求最小正整数解时用了模的方法来处理，值得细品 (x0%p+p)%p。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

int main()
{
 cin >> x >> y >> m >> n >> l;
 LL a = n-m, b = l, c = x-y, d, x0, y0;
 if (a < 0) {
 a = -a;
 c = -c;
 }
 exgcd(a, b, d, x0, y0);
 if (c % d == 0) {
 x0 *= c/d;
 y0 *= c/d;
 LL p = b/d;
 cout << (x0%p+p)%p << endl;
 } else {
 cout << "Impossible\n";
 }
 return 0;
}

POJ-2115 – C Looooops

可将题意转化为 $A+Ct\equiv B(mod\ 2^K)$，把它转化成方程：$A+Ct-B=2^Kz$，即 $Ct+2^Kz=B-A$，用 exgcd 解这个方程并求出 $t$ 的最小正整数解即为答案。

注意 1LL<<K，不开 long long 差点怀疑自己做错了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

while (cin >> A >> B >> C >> K && !(A==0&&B==0&&C==0&&K==0)) {
 K = 1ll<<K;
 LL a = C, b = K, d, x, y;
 exgcd(a, b, d, x, y);
 if (((B-A+K)%K)%d) {
 cout <<"FOREVER\n";
 } else {
 x *= ((B-A+K)%K)/d;
 LL p = b/d;
 x = (x%p+p)%p;
 cout << x << endl;
 }
}

模的逆

现在考虑特殊形式的同余方程 $ax\equiv 1(mod\ m)$。

由 定理 17，此方程有解当且仅当 $(a,m)=1$，于是其所有的解都模 $m$ 同余。

定义 8：给定整数 $a$，且满足 $(a,m)=1$，称 $ax\equiv 1(mod\ m)$ 的一个解为 $a$ 模 $m$ 的逆。

例：因为 $7x\equiv 1(mod\ 31)$ 的解满足 $x\equiv 9(mod\ 31)$，所以 $9$ 和所有与 $9$ 模 $31$ 同余的整数都是 $7$ 模 $31$ 的逆。类似地，因为 $9·7\equiv 1(mod\ 31)$，所以 $7$ 是 $9$ 模 $31$ 的逆。

当我们有 $a$ 模 $m$ 的一个逆时，可以用它来解形如 $ax\equiv b(mod\ m)$ 的任何同余方程。

为看清这一点，令 $\bar{a}$ 是 $a$ 的模 $m$ 的一个逆，所以 $a\bar{a}\equiv 1(mod\ m)$。

于是，若 $ax\equiv b(mod\ m)$，则根据 定理 12 将同余方程两边同时乘以 $\bar{a}$，得到 $\bar{a}(ax)\equiv \bar{a}b(mod\ m)$，所以 $x=\bar{a}b(mod\ m)$。

例 为求出 $7x\equiv 22(mod\ 31)$ 的所有解，我们在此方程两边同时乘以 $9$（这是 $7$ 模 $31$ 的一个逆），得 $9·7x\equiv 9·22(mod\ 31)$。因此，$x\equiv 198=12(mod\ 31)$。

求逆的三种算法：

1. 扩展欧几里得算法解同余方程，求单个逆。$ax\equiv 1(mod\ m)$ 等价于求二元线性不定方程的解：$ax+my=1$，其中 $(a,m)=1$ 是有逆的前提。只需要用扩展欧几里得算法求即可。

2. 费马小定理，求单个逆

定理 18（费马小定理）：设 $p$ 是一个素数，$a$ 是一个正整数且 $p\nmid a$，则 $a^{p-1}\equiv 1(mod\ p)$。

证明：考虑 $p-1$ 个整数 $a,2a,…,(p-1)a$，它们都不能被 $p$ 整除。因为若 $p \mid ja$, 那么因 $p \nmid a$，则由 引理 2 知 $p \mid j$，但 $1\le j\le p-1$，故这是不可能的。

现证明 $a,2a,…,(p-1)a$ 中任何两个整数模 $p$ 不同余。

为了证明这一点，设 $ja\equiv ka(mod\ p)$，其中 $1\le j\lt k\le p-1$。

那么根据 推论 3，因 $(a,p)=1$，故 $j\equiv k(mod\ p)$，但这也是不可能的，因为 $j$ 和 $k$ 都是小于 $p-1$ 的正整数.

因为整数 $a,2a,…,(p-1)a$ 是 $p-1$ 个满足模 $p$ 均不同余于 $0$ 且任何两个都互不同余的整数组成的集合中的元素，故由 引理 3 可知 $a,2a,…,(p-1)a$ 模 $p$ 的最小正剩按照一定的顺序必定是整数 $1,2,…,p-1$。

由同余性，整数 $a,2a,…,(p-1)a$ 的乘积模 $p$ 同余于前 $p-1$ 个正整数的乘积，即：

$a·2a·3a···(p-1)a \equiv 1·2·3···(p-1) (mod\ p)$

因此 $a^{p-1}(p-1)! \equiv (p-1)! (mod\ p)$， 因 $(p,(p-1)!)=1$，根据 推论 3，消去 $(p-1)!$，得到 $a^{p-1}\equiv 1(mod\ p)$，证毕。

利用费马小定理，$a^{p-1}\equiv 1(mod\ p)$，则 $a·a^{p-2} \equiv 1(mod\ p)$，即 $a^{p-2}$ 是 $a$ 模 $p$ 的一个逆。

注意前提：$p$ 是一个素数，$a$ 是一个正整数且 $p \nmid a$。

通常可以用快速幂求 $a^{p-2}$。

3. 若 $p$ 是素数，$n\lt p$，线性递推求 $1$ 至 $n$ 在模 $p$ 意义下的乘法逆元

首先，$i=1$ 的逆是 $1$。下面求 $i\gt 1$ 的逆，用递推法。

1. 用带余除法 $p = k·i + r$，其中 $0\le r \lt i$，故 $k·i + r \equiv 0 (mod\ p)$
2. 在等式两边乘 $i^{-1}r^{-1}$，即 $(k·i + r)·i^{-1}r^{-1} \equiv 0 (mod\ p)$，即 $kr^{-1} + i^{-1} \equiv 0 (mod\ p)$
3. 移项得 $i^{-1}\equiv -kr^{-1} (mod\ p)$，即 $i^{-1}\equiv (-p/i)r^{-1} (mod\ p)$。若要避免负数，因 $pr^{-1} \equiv 0 (mod\ p)$，由定理 12 得，$pr^{-1} + (-p/i)r^{-1} \equiv (-p/i)r^{-1} (mod\ p)$ ，即 $(p-p/i)r^{-1} \equiv (-p/i)r^{-1} (mod\ p) $。

则 $i^{-1}\equiv (p-p/i)r^{-1} (mod\ p)$。

代码：

1
2
3
4

void inverse(LL n, LL p) {
 inv[1] = 1;
 for (int i = 2; i <= n; i++) inv[i] = (p-p/i)*inv[p%i]%p;
}

逆与除法取模

逆的一个重要应用是求除法的模。求 $(a/b) \bmod m$，即 $a$ 除以 $b$，然后对 $m$ 取模。

这里 $a$ 和 $b$ 都是很大的数，如 $a=n!$，容易溢出，导致取模出错。

用逆可以避免除法计算，设 $b$ 的逆元是 $b^{-1}$，有 $(a/b) \bmod m = ((a/b) \bmod m) ((bb^{-1}) \bmod m) = (a/b×bb^{-1}) \bmod m = (ab^{-1}) \bmod m$

经过上述推导，除法的模运算转换为乘法模运算，即

$(a/b) \bmod m = (ab^{-1}) \bmod m = (a \bmod m) (b^{-1} \bmod m) \bmod m$

习题

HDU-1576 A/B 因为 $\gcd(B,9973)=1$，可以用 exgcd 求逆元。

1
2
3
4
5
6
7
8
9

while (t--) {
 LL n, B;
 cin >> n >> B;
 LL a, b, d, x, y;
 exgcd(B, 9973, d, x, y);
 LL p = 9973;
 x = (x%p+p)%p;
 cout << n*x%9973 << endl;
}

更多资料

• 数学：Exgcd 与乘法逆元的漫步 - Aw顿顿の小窝 · Linear Expectation 线性期望 【数论】Exgcd/乘法逆元 - 题单

ABC209F Deforestation

题意：给出 $n$ 棵树的高度，砍第 $i$ 棵树的花费是 $h_i+h_{i-1}+h_{i+1}$，求有多少种方案能使得砍完所有树的总代价最小。

砍一棵树的代价只与相邻的树高度有关。下面研究砍 $h_i$ 与 $h_{i+1}$ 的先后顺序对答案的影响。

1. 先砍 $h_i$ 后砍 $h_{i+1}$：$h_i+h_{i-1}+h_{i+1}+h_{i+1}+h_{i+2}$
2. 先砍 $h_{i+1}$ 后砍 $h_i$：$h_{i+1}+h_i+h_{i+2}+h_i+h_{i-1}$

作差后得到：$h_{i+1}-h_i$。当 $h_{i+1}>h_i$ 时，应该先砍 $h_{i+1}$。当 $h_{i+1}<h_i$ 时，应该先砍 $h_i$。因此，对于相邻的两棵树，先砍高的那棵最优。

插入 DP（insertion DP）：先考虑排好前 $i-1$ 个数，再往中间插入第 $i$ 个数。

令 $\mathit{f}_{i,j}$ 表示排好了前 $i$ 棵树的砍树次序，且第 $i$ 棵树排在第 $j$ 位，得到最小代价的方案数。

当 $h_{i+1} > h_i$ 时，应先砍 $i+1$，那么 $\mathit{f}{i+1,j} = \sum{k=j}^{i}\mathit{f}_{i,k}$

当 $h_i > h_{i+1}$ 时，应先砍 $i$，那么 $\mathit{f}{i+1,j} = \sum{k=1}^{j-1}\mathit{f}_{i,k}$

当 $h_i = h_{i+1}$ 时，砍哪棵都可以，$\mathit{f}{i+1,j} = \sum{k=1}^i\mathit{f}_{i,k}$

可以用前缀和优化 DP，$O(n^2)$。

弱智错误！：减法忘记加 MOD。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1e9+7;
LL n, h[4005];
LL dp[4005][4005], sum[4005][4005];
int main()
{
 cin >> n;
 for (int i = 1; i <= n; i++) cin >> h[i];
 dp[1][1] = sum[1][1] = 1;
 for (int i = 2; i <= n; i++) {
 for (int j = 1; j <= i; j++) {
 if (h[i] > h[i-1]) {
 dp[i][j] = (sum[i-1][i-1]-sum[i-1][j-1]+MOD)%MOD;
 } else if (h[i] < h[i-1]) {
 dp[i][j] = (sum[i-1][j-1])%MOD;
 } else {
 dp[i][j] = (sum[i-1][i-1])%MOD;
 }
 sum[i][j] = (sum[i][j-1]+dp[i][j])%MOD;
 }
 }
 LL ans = 0;
 for (int i = 1; i <= n; i++) ans = (ans+dp[n][i])%MOD;
 cout << ans << endl;
 return 0;
}

Thanks to ABC 209 F - Deforestation - hzy0227

基本思想

CDQ 分治的基本思想十分简单。如下：

1. 我们要解决一系列问题，这些问题一般包含修改和查询操作，可以把这些问题排成一个序列，用一个区间 $[L,R]$ 表示。
2. 分。递归处理左边区间 $[L,M]$ 和右边区间 $[M+1,R]$ 的问题。
3. 治。合并两个子问题，同时考虑到 $[L,M]$ 内的修改对 $[M+1,R]$ 内的查询产生的影响。即，用左边的子问题帮助解决右边的子问题。

这就是 CDQ 分治的基本思想。和普通分治不同的地方在于，普通分治在合并两个子问题的过程中，$[L,M]$ 内的问题不会对 $[M+1,R]$ 内的问题产生影响。

前置知识：二维偏序

给定 $N$ 个有序对 $(a,b)$，求对于每个 $(a,b)$，满足 $a2<a$ 且 $b2<b$ 的有序对 $(a2,b2)$ 有多少个。

可以将归并排序求逆序对的思路套用过来，这题实际上就是求顺序对。首先根据 $a$ 的大小排序，然后归并排序 $b$，这样就可以忽略 $a$ 元素的影响，因为左边区间的元素的 $a$ 一定小于右边元素的 $a$。归并排序时，每次从右边区间的有序序列取一个元素，然后求左边区间多少个元素比它小即可。

更浅显的解法是，用树状数组代替 CDQ 分治。这里就不赘述。

放个求逆序对的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

void mergesort(int l, int r) {
 if (l >= r) return ;
 int mid = (l+r)/2;
 mergesort(l, mid);
 mergesort(mid+1, r);
 int lp = l, rp = mid+1;
 int i = l;
 while (lp <= mid && rp <= r) {
 if (a[lp] > a[rp]) {
 ans += mid-lp+1;
 b[i++] = a[rp++];
 } else {
 b[i++] = a[lp++];
 }
 }
 while (lp <= mid) b[i++] = a[lp++];
 while (rp <= r) b[i++] = a[rp++];
 for (int i = l; i <= r; i++)
 a[i] = b[i];
}

例题

一：三维偏序

Luogu-P3810 【模板】三维偏序（陌上花开）

给定 $N$ 个有序三元组 $(a,b,c)$，求对于每个三元组 $(a,b,c)$，有多少个三元组$(a2,b2,c2)$ 满足$a2<a$ 且 $b2<b$ 且 $c2<c$。

同样地，我们要保证前两维的顺序，才可以计算出答案。

先按 $a$ 进行排序，然后在归并过程中按 $b$ 排序，但是此时不能像求逆序对一样利用下标轻松地统计个数了。

怎么办呢？我们可以维护 $c$ 的树状数组。如果 $b2 \le b$，那么 $c2$ 就可以对以后的 $b$ 产生贡献了，把 $c2$ 加入树状数组。统计时查询树状数组中 $c$ 的前缀和即可。

时间复杂度：$T(n)=O(n\log k)+T(\frac 2 n)=O(n\log n\log k)$

有一些细节问题：

• 每次处理完后，树状数组清零不要用 memset，否则会超时。要一个一个减去。
• 可能有完全相同的元素。本来它们相互之间都有贡献，可是 CDQ 的过程中只有左边的能贡献右边的。所以需要进行去重处理。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include <bits/stdc++.h>
using namespace std;
struct node {
 int a, b, c;
 int cnt, ans;
} a[100005], b[100005];
bool cmp1(node a, node b) {
 if (a.a != b.a) return a.a < b.a;
 if (a.b != b.b) return a.b < b.b;
 return a.c < b.c;
}
bool cmp2(node a, node b) {
 if (a.b != b.b) return a.b < b.b;
 return a.c < b.c;
}
int n, k, m;
int tree[200005], ans[200005];
int lowbit(int x) { return x&(-x); }
int query(int x) {
 int ret = 0;
 while (x) {
 ret += tree[x];
 x -= lowbit(x);
 }
 return ret;
}
void add(int x, int y) {
 while (x <= k) {
 tree[x] += y;
 x += lowbit(x);
 }
}
void cdq(int l, int r) {
 if (l == r) return;
 int mid = (l+r)>>1;
 cdq(l, mid);
 cdq(mid+1, r);
 sort(b+l, b+mid+1, cmp2);
 sort(b+mid+1, b+r+1, cmp2);
 int p = l, q = mid+1;
 while (q <= r) {
 while (p <= mid && b[p].b <= b[q].b) {
 add(b[p].c, b[p].cnt);
 p++;
 }
 b[q].ans += query(b[q].c);
 q++;
 }
 for (int i = l; i < p; i++) add(b[i].c, -b[i].cnt);// 拒绝 memset！
}
int main()
{
 cin >> n >> k;
 for (int i = 1; i <= n; i++) cin >> a[i].a >> a[i].b >> a[i].c;
 sort(a+1, a+1+n, cmp1);
 for (int i = 1; i <= n; i++) {
 int j = i;
 while (a[j+1].a == a[i].a && a[j+1].b == a[i].b && a[j+1].c == a[i].c) j++;
 b[++m] = a[i];
 b[m].cnt = j-i+1;
 i = j;
 }
 cdq(1, m);
 for (int i = 1; i <= m; i++)
 ans[b[i].ans+b[i].cnt-1] += b[i].cnt;
 for (int i = 0; i < n; i++) cout << ans[i] << endl;
 return 0;
}

二：天使玩偶/SJY 摆棋子

Luogu-P4169 Violet 天使玩偶/SJY 摆棋子

要算的 $dist(A,B)=|A_x-B_x|+|A_y-B_y|$ 有绝对值，为了简化问题，可以把原来的询问分成四个，分别计算在 $(x,y)$ 的左下、左上、右下、右上方向上距离最近的点有多远，再去最小值即为答案。

以左下方向为例，化简后得到 $(x+y)-\max(x_i+y_i)$，若扫描到一个点 $(x_i, y_i)$，则在树状数组中把 $y_i$ 位置上的值与 $x_i+y_i$ 取最大值，扫描到询问时，则求 $[0, y_i]$ 上的最大值 $val$，该询问（左下方向）的答案就是 $x+y-val$。简言之，套 CDQ，按照 $x$ 进行排序，然后树状数组处理 $y$。

对于另外三个方向，可以进行翻转后转换成左下方向。记所有点最大的 $x$ 或 $y$ 为 $maxxy$，例如将右上方向翻到左下方向时，坐标变成 $(maxxy-x, maxxy-y)$。为了避免出现 $0$ 使树状数组爆炸，可以将所有 $x$ 和 $y$ 值 $+1$，$maxxy$ 也要 $+1$。

要在 CDQ 过程中对 $x$ 进行归并排序，sort 太慢。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

#include <bits/stdc++.h>
using namespace std;
const int N = 3000005;
struct node {
 int type, x, y, id, ans;
} a[N], b[N], tmp[N];
int n, m, maxxy;
int tree[N];
int lowbit(int x) { return x&(-x); }
int query(int x) {
 int ret = 0;
 while (x) {
 ret = max(ret, tree[x]);
 x -= lowbit(x);
 }
 return ret ? ret : -1e9;
}
void upd(int x, int y) {
 while (x <= maxxy) {
 tree[x] = max(y, tree[x]);
 x += lowbit(x);
 }
}
void clear(int x) {
 while (x <= maxxy) {
 tree[x] = 0;
 x += lowbit(x);
 }
}
void cdq(int l, int r) {
 if (l == r) return;
 int mid = (l+r)>>1;
 cdq(l, mid);
 cdq(mid+1, r);
 int p = l, q = mid+1, t = l;
 while (q <= r) {
 while (p <= mid && b[p].x <= b[q].x) {
 if (b[p].type == 1)
 upd(b[p].y, b[p].x+b[p].y);
 tmp[t++] = b[p++];
 }
 if (b[q].type == 2)
 a[b[q].id].ans = min(a[b[q].id].ans, b[q].x+b[q].y-query(b[q].y));
 tmp[t++] = b[q++];
 }
 for (int i = l; i < p; i++) if (b[i].type == 1) clear(b[i].y);
 while (p <= mid) tmp[t++] = b[p++];
 for (int i = l; i <= r; i++) b[i] = tmp[i];
}
int main()
{
 cin >> n >> m;
 for (int i = 1; i <= n; i++) {
 cin >> a[i].x >> a[i].y;
 a[i].x++;
 a[i].y++;
 a[i].type = 1;
 a[i].id = i;
 maxxy = max(maxxy, max(a[i].x, a[i].y));
 }
 for (int i = n+1; i <= n+m; i++) {
 cin >> a[i].type >> a[i].x >> a[i].y;
 a[i].x++;
 a[i].y++;
 a[i].id = i;
 a[i].ans = 1e9;
 maxxy = max(maxxy, max(a[i].x, a[i].y));
 }
 maxxy++;

 for (int i = 1; i <= n+m; i++) b[i] = a[i];
 cdq(1, n+m);
 for (int i = 1; i <= n+m; i++) {
 b[i] = a[i];
 b[i].x = maxxy-a[i].x;
 b[i].y = maxxy-a[i].y;
 }
 cdq(1, n+m);
 for (int i = 1; i <= n+m; i++) {
 b[i] = a[i];
 b[i].x = maxxy-a[i].x;
 }
 cdq(1, n+m);
 for (int i = 1; i <= n+m; i++) {
 b[i] = a[i];
 b[i].y = maxxy-a[i].y;
 }
 cdq(1, n+m);

 for (int i = n+1; i <= n+m; i++)
 if (a[i].type == 2) cout << a[i].ans << endl;

 return 0;
}