# 模运算中的除法技巧

## 1. 问题背景

在算法竞赛或编程中，经常需要计算形如

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

的结果，其中 $A$ 和 $B$ 可能非常大（例如达到 $10^{18}$），直接计算 $A \times B$ 会导致整数溢出。同时，由于模数 $10$ 与除数 $2$ 不互质，不能简单地对 $A$ 和 $B$ 分别取模 $10$ 后再相乘除以 $2$。

本文给出一种通用的取模除法技巧，能够在不溢出的前提下正确计算结果。

## 2. 核心性质

**性质**：设 $A, B$ 为整数，且 $A \times B$ 能被 $2$ 整除。则

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

其中右边的除法是整数除法（因为分子必为偶数）。

更一般地，对于正整数 $k$ 和 $m$，若 $k \mid (A \times B)$，则

$$
\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}
$$

## 3. 数学证明

我们证明 $k = 2, m = 10$ 的情形。

设

$$
A = 20a + r\_1, \quad 0 \le r\_1 < 20
$$
$$
B = 20b + r\_2, \quad 0 \le r\_2 < 20
$$

其中 $a, b$ 为整数，$r\_1 = A \bmod 20$，$r\_2 = B \bmod 20$。

计算 $A \times B$：

$$
A \times B = (20a + r\_1)(20b + r\_2)
= 400ab + 20a r\_2 + 20b r\_1 + r\_1 r\_2
$$

两边除以 $2$：

$$
\frac{A \times B}{2}
= 200ab + 10a r\_2 + 10b r\_1 + \frac{r\_1 r\_2}{2}
$$

注意 $r\_1 r\_2$ 是偶数（因为 $A \times B$ 是偶数，而 $400ab, 20a r\_2, 20b r\_1$ 都是偶数，所以 $r\_1 r\_2$ 必为偶数）。

现在对 $10$ 取模：

$$
\left( \frac{A \times B}{2} \right) \bmod 10
=
\left( 200ab + 10a r\_2 + 10b r\_1 + \frac{r\_1 r\_2}{2} \right) \bmod 10
$$

前三个项都是 $10$ 的倍数，因此对 $10$ 取模为 $0$。所以

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

另一方面，考虑

$$
(r\_1 \times r\_2) \bmod 20
$$

因为 $r\_1 r\_2$ 是偶数，设 $r\_1 r\_2 = 2q$，则

$$
(r\_1 r\_2) \bmod 20 = 2q \bmod 20 = 2(q \bmod 10)
$$

因此

$$
\frac{(r\_1 r\_2) \bmod 20}{2} = q \bmod 10 = \left( \frac{r\_1 r\_2}{2} \right) \bmod 10
$$

这就证明了

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

证毕。

## 4. 推广形式

对于一般情况：

$$
\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$ 取模，即可得到结论。

## 5. 应用示例

### 5.1 题目背景

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

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

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

### 5.2 使用技巧

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

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

根据性质：

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

### 5.3 代码实现

```cpp
long long a = (x - 1) % 20;
long long b = (2 * N + 2 - x) % 20;
long long before = ((a * b) % 20) / 2; // 前 x-1 行总数 mod 10
```

模运算中的除法技巧

1. 问题背景

在算法竞赛或编程中，经常需要计算形如

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

本文给出一种通用的取模除法技巧，能够在不溢出的前提下正确计算结果。

2. 核心性质

性质：设 $A, B$ 为整数，且 $A \times B$ 能被 $2$ 整除。则

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

其中右边的除法是整数除法（因为分子必为偶数）。

更一般地，对于正整数 $k$ 和 $m$，若 $k \mid (A \times B)$，则

$$ \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} $$

3. 数学证明

我们证明 $k = 2, m = 10$ 的情形。

设

$$ A = 20a + r_1, \quad 0 \le r_1 < 20 $$ $$ B = 20b + r_2, \quad 0 \le r_2 < 20 $$

其中 $a, b$ 为整数，$r_1 = A \bmod 20$，$r_2 = B \bmod 20$。

计算 $A \times B$：

$$ A \times B = (20a + r_1)(20b + r_2) = 400ab + 20a r_2 + 20b r_1 + r_1 r_2 $$

两边除以 $2$：

$$ \frac{A \times B}{2} = 200ab + 10a r_2 + 10b r_1 + \frac{r_1 r_2}{2} $$

注意 $r_1 r_2$ 是偶数（因为 $A \times B$ 是偶数，而 $400ab, 20a r_2, 20b r_1$ 都是偶数，所以 $r_1 r_2$ 必为偶数）。

现在对 $10$ 取模：

$$ \left( \frac{A \times B}{2} \right) \bmod 10 = \left( 200ab + 10a r_2 + 10b r_1 + \frac{r_1 r_2}{2} \right) \bmod 10 $$

前三个项都是 $10$ 的倍数，因此对 $10$ 取模为 $0$。所以

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

另一方面，考虑

$$ (r_1 \times r_2) \bmod 20 $$

因为 $r_1 r_2$ 是偶数，设 $r_1 r_2 = 2q$，则

$$ (r_1 r_2) \bmod 20 = 2q \bmod 20 = 2(q \bmod 10) $$

因此

$$ \frac{(r_1 r_2) \bmod 20}{2} = q \bmod 10 = \left( \frac{r_1 r_2}{2} \right) \bmod 10 $$

这就证明了

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

证毕。

4. 推广形式

对于一般情况：

$$ \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$ 取模，即可得到结论。

5. 应用示例

5.1 题目背景

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

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

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

5.2 使用技巧

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

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

根据性质：

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

5.3 代码实现

long long a = (x - 1) % 20;
long long b = (2 * N + 2 - x) % 20;
long long before = ((a * b) % 20) / 2; // 前 x-1 行总数 mod 10

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com