# 同余性质讲义：模运算中的尺度缩放

## 1. 引言

在算法竞赛和程序设计中，我们经常需要处理大整数取模的问题。当数字非常大时，直接计算乘积会导致溢出，而模运算中的除法又不能随意分配。本文介绍一个基础但极其重要的同余性质：

$$
(k \cdot q) \bmod (k \cdot m) = k \cdot (q \bmod m)
$$

其中 $k, m$ 为正整数，$q$ 为整数。这个性质在避免大数溢出、优化计算时非常有用。

---

## 2. 性质陈述

**性质**：对于任意正整数 $k, m$ 和整数 $q$，有

$$
(k \cdot q) \bmod (k \cdot m) = k \cdot (q \bmod m)
$$

**同余形式**：

$$
k \cdot q \equiv k \cdot (q \bmod m) \pmod{k \cdot m}
$$

由于两边都在 $[0, k \cdot m)$ 范围内，同余直接变成相等。

---

## 3. 数学证明

### 3.1 取模语言证明

设 $q = m \cdot t + r$，其中 $0 \le r < m$，且 $r = q \bmod m$。

则

$$
k \cdot q = k(m \cdot t + r) = k \cdot m \cdot t + k \cdot r
$$

因为 $0 \le k \cdot r < k \cdot m$，所以

$$
(k \cdot q) \bmod (k \cdot m) = k \cdot r = k \cdot (q \bmod m)
$$

证毕。

### 3.2 同余语言证明

由 $q \equiv r \pmod{m}$，两边同乘 $k$，得

$$
k \cdot q \equiv k \cdot r \pmod{k \cdot m}
$$

即

$$
k \cdot q \equiv k \cdot (q \bmod m) \pmod{k \cdot m}
$$

又因为两边都在 $[0, k \cdot m)$ 内，故相等。

---

## 4. 直观理解

### 4.1 周期缩放

想象一个周长为 $m$ 的圆环，从起点走 $q$ 步，最终停在离起点 $q \bmod m$ 的位置。

现在把整个圆环放大 $k$ 倍，周长变成 $k \cdot m$。同时，走的步数也放大 $k$ 倍，变成 $k \cdot q$ 步。那么最终停在离起点 $k \cdot (q \bmod m)$ 的位置。

因为整个系统的尺度放大了 $k$ 倍，所以最终位置的坐标也放大了 $k$ 倍。

### 4.2 钟表例子

- 一圈有 $10$ 个刻度（$m = 10$），走 $13$ 步（$q = 13$），$13 \bmod 10 = 3$，停在刻度 $3$。
- 把钟表放大：一圈有 $20$ 个刻度（$k = 2$，$m = 10$），走 $26$ 步（$k \cdot q = 26$），$26 \bmod 20 = 6$，停在刻度 $6$。
- 而 $6 = 2 \times 3$，正好是原来刻度 $3$ 的两倍。

### 4.3 分组视角

把整数按每 $m$ 个分成一组：

$$
0, 1, 2, \dots, m-1 \quad | \quad m, m+1, \dots, 2m-1 \quad | \quad \dots
$$

$q \bmod m$ 表示 $q$ 在它所在组内的偏移量。

现在把每组的大小扩大 $k$ 倍，变成每 $k \cdot m$ 个一组。同时把 $q$ 也乘以 $k$。那么原来在组内的偏移量也会乘以 $k$，因为每个位置之间的距离都拉大了 $k$ 倍。

---

## 5. 物理意义

这个性质的物理意义可以理解为：**周期和位置同比例缩放时，相对位置也同比例缩放**。

> 当循环周期从 $m$ 放大到 $k \cdot m$，同时步长（或计数值）也从 $q$ 放大到 $k \cdot q$ 时，最终落在周期内的相对位置（余数）也会放大 $k$ 倍。

它本质上是一种“尺度变换”下的不变性——相对位置的比例保持不变，只是绝对数值被放大了。在算法中，利用这个性质，我们可以先对较小的数取模，再乘以 $k$，从而避免大数运算溢出。

---

## 6. 应用：避免大数溢出

### 6.1 问题背景

在“数数”问题中，需要计算前 $x-1$ 行的总星星数 $S$ 对 $10$ 取模：

$$
S = \frac{(x-1)(2N + 2 - x)}{2}
$$

其中 $N$ 可达 $10^{18}$，直接计算 $(x-1)(2N+2-x)$ 会溢出。

### 6.2 使用技巧

令 $A = x-1$，$B = 2N + 2 - x$，则

$$
S \bmod 10 = \left( \frac{A \times B}{2} \right) \bmod 10
$$

由性质（取 $k=2, m=10$）：

$$
\left( \frac{A \times B}{2} \right) \bmod 10
=
\frac{(A \bmod 20) \times (B \bmod 20) \bmod 20}{2}
$$

### 6.3 计算步骤

1. 分别计算 $A \bmod 20$ 和 $B \bmod 20$。
2. 将两个余数相乘，并对 $20$ 取模。
3. 将结果除以 $2$，得到 $S \bmod 10$。
4. 再加上当前行的偏移 $(y-1) \bmod 10$，最后对 $10$ 取模，即为答案。

这样既避免了溢出，又得到了正确结果。

---

## 7. 推广形式

对于一般情况：

$$
\left( \frac{A \times B}{k} \right) \bmod m
=
\frac{(A \bmod (k \cdot m)) \times (B \bmod (k \cdot m)) \bmod (k \cdot m)}{k}
$$

**条件**：$k \mid (A \times B)$，且 $k, m$ 为正整数。

**证明思路**：将 $A$ 和 $B$ 分别表示为 $k \cdot m$ 的倍数加上余数，展开后除以 $k$，对 $m$ 取模，即可得到结论。

---

## 8. 总结

- 核心性质：$(k \cdot q) \bmod (k \cdot m) = k \cdot (q \bmod m)$。
- 它既是同余性质，也是模运算的恒等变形。
- 物理意义：周期和步长同比例放大时，余数也同比例放大。
- 应用：在大数取模除法中，先对 $k \cdot m$ 取模，再相乘取模，最后除以 $k$，避免溢出。
- 推广：可处理 $(A \times B / k) \bmod m$ 的一般情形。

掌握这个性质，可以让你在处理大数模运算时更加从容，写出高效且正确的代码。

---

## 9. 参考文献

- 数论中的模运算基本性质
- 算法竞赛中的大数取模技巧

同余性质讲义：模运算中的尺度缩放

1. 引言

$$ (k \cdot q) \bmod (k \cdot m) = k \cdot (q \bmod m) $$

其中 $k, m$ 为正整数，$q$ 为整数。这个性质在避免大数溢出、优化计算时非常有用。

2. 性质陈述

性质：对于任意正整数 $k, m$ 和整数 $q$，有

$$ (k \cdot q) \bmod (k \cdot m) = k \cdot (q \bmod m) $$

同余形式：

$$ k \cdot q \equiv k \cdot (q \bmod m) \pmod{k \cdot m} $$

由于两边都在 $[0, k \cdot m)$ 范围内，同余直接变成相等。

3. 数学证明

3.1 取模语言证明

设 $q = m \cdot t + r$，其中 $0 \le r < m$，且 $r = q \bmod m$。

则

$$ k \cdot q = k(m \cdot t + r) = k \cdot m \cdot t + k \cdot r $$

因为 $0 \le k \cdot r < k \cdot m$，所以

$$ (k \cdot q) \bmod (k \cdot m) = k \cdot r = k \cdot (q \bmod m) $$

证毕。

3.2 同余语言证明

由 $q \equiv r \pmod{m}$，两边同乘 $k$，得

$$ k \cdot q \equiv k \cdot r \pmod{k \cdot m} $$

即

$$ k \cdot q \equiv k \cdot (q \bmod m) \pmod{k \cdot m} $$

又因为两边都在 $[0, k \cdot m)$ 内，故相等。

4. 直观理解

4.1 周期缩放

想象一个周长为 $m$ 的圆环，从起点走 $q$ 步，最终停在离起点 $q \bmod m$ 的位置。

现在把整个圆环放大 $k$ 倍，周长变成 $k \cdot m$。同时，走的步数也放大 $k$ 倍，变成 $k \cdot q$ 步。那么最终停在离起点 $k \cdot (q \bmod m)$ 的位置。

因为整个系统的尺度放大了 $k$ 倍，所以最终位置的坐标也放大了 $k$ 倍。

4.2 钟表例子

一圈有 $10$ 个刻度（$m = 10$），走 $13$ 步（$q = 13$），$13 \bmod 10 = 3$，停在刻度 $3$。
把钟表放大：一圈有 $20$ 个刻度（$k = 2$，$m = 10$），走 $26$ 步（$k \cdot q = 26$），$26 \bmod 20 = 6$，停在刻度 $6$。
而 $6 = 2 \times 3$，正好是原来刻度 $3$ 的两倍。

4.3 分组视角

把整数按每 $m$ 个分成一组：

$$ 0, 1, 2, \dots, m-1 \quad | \quad m, m+1, \dots, 2m-1 \quad | \quad \dots $$

$q \bmod m$ 表示 $q$ 在它所在组内的偏移量。

5. 物理意义

这个性质的物理意义可以理解为：周期和位置同比例缩放时，相对位置也同比例缩放。

当循环周期从 $m$ 放大到 $k \cdot m$，同时步长（或计数值）也从 $q$ 放大到 $k \cdot q$ 时，最终落在周期内的相对位置（余数）也会放大 $k$ 倍。

6. 应用：避免大数溢出

6.1 问题背景

在“数数”问题中，需要计算前 $x-1$ 行的总星星数 $S$ 对 $10$ 取模：

$$ S = \frac{(x-1)(2N + 2 - x)}{2} $$

其中 $N$ 可达 $10^{18}$，直接计算 $(x-1)(2N+2-x)$ 会溢出。

6.2 使用技巧

令 $A = x-1$，$B = 2N + 2 - x$，则

$$ S \bmod 10 = \left( \frac{A \times B}{2} \right) \bmod 10 $$

由性质（取 $k=2, m=10$）：

$$ \left( \frac{A \times B}{2} \right) \bmod 10 = \frac{(A \bmod 20) \times (B \bmod 20) \bmod 20}{2} $$

6.3 计算步骤

分别计算 $A \bmod 20$ 和 $B \bmod 20$。
将两个余数相乘，并对 $20$ 取模。
将结果除以 $2$，得到 $S \bmod 10$。
再加上当前行的偏移 $(y-1) \bmod 10$，最后对 $10$ 取模，即为答案。