培玉 · 一试

专题地图 › 数论

数论

从这里开始

整数变形后，回头检查合法性

说明整除或同余变形用到了哪些前提，穷尽候选并按原来的整数范围与计数口径核对。

带我练直接挑战

看知识图谱

本专题核心公式速查

互动实验：取整阶梯与勒让德计数 · 剩余系、原根与同余轮盘

数论题的对象是整数，但入口常藏在集合、对数、数列或几何量里。先问哪一条条件真正使用了整数性：可能是因数只能取有限值，可能是平方的余数，也可能是互素参数的结构。本站从同余、因数分解和最大公约数起步，再练周期计数、数位与递推；每次分类都要交代范围、边界和反向验证。

1. 先修与破题直觉：先找出哪一条条件用到了整数性。 $x y + x + y = 11$ 补常数得 $(x + 1) (y + 1) = 12$ ；正整数解要求两个因数都至少为 $2$ ，所以只能取 $2 \cdot 6, 3 \cdot 4, 4 \cdot 3, 6 \cdot 2$ ，即 $(x, y) = (1, 5), (2, 3), (3, 2), (5, 1)$ 。

2. 核心条件辨析：同余式两边约去 $c$ ，只有在 $g cd (c, m) = 1$ 时模数才不变，否则模数要除以 $g cd (c, m)$ ； $n!$ 中素因子 $p$ 的指数要把 $p, p^{2}, p^{3}, \dots$ 的倍数分层累加；递推数列模 $m$ 的周期要看相邻项组成的完整状态；整数平方模 $4$ 只取 $0, 1$ 。

3. 典型误区对比：先读末尾零只数 $5$ 的倍数、把单项余数 $0$ 的间隔当周期两组红绿卡，再做自测。每次分类都写出范围和边界，并反向验证。

4. 方法迁移带练：勒让德（Legendre）公式： $v_{5} (200!) = 40 + 8 + 1 = 49$ ； $v_{2} (10!) = 5 + 2 + 1 = 8$ ，而 $10 = (1010)_{2}$ 的数码和为 $2$ ， $10 - 2 = 8$ 一致。同余约分： $6 x \equiv 4 (mod 10)$ 约去公因子 $2$ 要连模数一起除，得 $3 x \equiv 2 (mod 5)$ ，即 $x \equiv 4 (mod 5)$ ；若误写成 $3 x \equiv 2 (mod 10)$ ，只剩 $x \equiv 4 (mod 10)$ ，会漏掉 $x = 9$ 这类解（ $6 \cdot 9 = 54 \equiv 4 (mod 10)$ ）。

5. 分级真题实战：先练“添项配积与因数配对”和“选模、剩余类与局部排除”，再练“素因数指数与算术函数”“公因子归一与欧几里得变形”；之后进入“分块、容斥与累计计数”“排序限界与有限分类”，最后挑战“递推状态与不变量”和“位值展开与数位约束”。

先修（培玉高中数学）：二次函数与一元二次方程、不等式等比数列数学归纳法（选学）

知识要点

同余是按余数压缩整数

写 $a = q m + r$ ，其中 $0 \leq r < m$ ，就把整数分到模 $m$ 的剩余类； $a \equiv b (mod m)$ 等价于 $m ∣ a - b$ 。例如 $23 = 4 \cdot 5 + 3$ ，所以 $23 \equiv 3 (mod 5)$ 。同余式可以相加、相乘，但约去一个因子前必须确认它与模数互素；否则会丢失合法情形。

唯一分解把完全幂变成指数条件

正整数的素因数分解唯一。若 $N = \prod p_{i}^{e_{i}}$ ，则 $N$ 是完全 $k$ 次幂，当且仅当每个 $e_{i}$ 都被 $k$ 整除；正因数个数为 $\prod (e_{i} + 1)$ 。例如 $72 = 2^{3} \cdot 3^{2}$ 有 $12$ 个正因数，乘以 $2$ 后成为平方数 $144$ 。互素分解还使因数和、欧拉函数等量可以分开计算： $σ (72) = 195$ ， $φ (72) = 24$ 。

最大公约数与最小公倍数先归一化

设 $d = g cd (a, b)$ ，写成 $a = d x, b = d y$ ，其中 $g cd (x, y) = 1$ ，则 $lcm (a, b) = d x y$ ，且 $ab = d lcm (a, b)$ 。例如 $18 = 6 \cdot 3, 30 = 6 \cdot 5$ ，两数的最小公倍数为 $90$ 。互素性允许把整除一个乘积的条件转到单个因子上；化简后还须检查参数是否满足原来的互素要求。

配成乘积后，整数条件成为因数条件

整数方程中同时出现乘积与一次项时，可试着补常数。例： $x y + x + y = 23$ 等价于 $(x + 1) (y + 1) = 24$ ，于是正整数解来自有限的正因数对，如 $3 \cdot 8$ 对应 $(x, y) = (2, 7)$ 。分式方程须先列出分母非零条件；清分母、平方或约分后都要回代，避免把零分母或错误符号纳入答案。

平方剩余与相邻平方的间隙

整数平方模 $4$ 只有 $0, 1$ ，奇数平方模 $8$ 恒为 $1$ ；因此平方差不可能模 $4$ 余 $2$ ，例如 $x^{2} - y^{2} = 14$ 没有整数解。若一个平方只比 $a^{2}$ 大少量，可写成 $(a + r)^{2}$ ，利用增量 $2 a r + r^{2}$ 限制正整数 $r$ 。同余适合整体排除，平方间隙适合把无限可能压到少数分支。

幂的周期与模递推数列的完整状态

当底数与模数互素时，幂的余数会周期重复（由欧拉定理 $a^{φ (m)} \equiv 1 (mod m)$ ，最小正周期即阶 $ord_{m} (a) ∣ φ (m)$ ）。例： $2, 2^{2}, 2^{3}$ 模 $7$ 的余数依次为 $2, 4, 1$ ，故 $2^{20} \equiv 4 (mod 7)$ 。递推数列模 $m$ 时不能只因某一项余数重复就宣布周期； $k$ 阶递推应记录连续 $k$ 项的有序元组 $(u_{n}, \dots, u_{n + k - 1}) mod m$ （至多 $m^{k}$ 种状态）。只有完整状态回到原处，后续才重复；若线性递推 $u_{n + k} \equiv c_{1} u_{n + k - 1} + \dots + c_{k} u_{n} (mod m)$ 满足首尾系数互素 $g cd (c_{k}, m) = 1$ ，则状态转移可逆，有限状态轨道从首项起即为纯周期，没有额外的非周期开头。

高斯取整、勒让德（Legendre）公式与周期累计计数

在 $[1, n]$ 中能被正整数 $d$ 整除的整数恰有 $⌊ n / d ⌋$ 个。由此分层统计素数幂倍数，即得阶乘素因数指数的勒让德（Legendre）公式：

v_{p} (n!) = k = 1 \sum \infty ⌊ \frac{n}{p ^{k}} ⌋ = \frac{n - s _{p} ( n )}{p - 1},

其中 $s_{p} (n)$ 为 $n$ 在 $p$ 进制下的各位数字之和；进而二项式系数满足库默尔（Kummer）定理 $v_{p} (a a + b) = \frac{s _{p} ( a ) + s _{p} ( b ) - s _{p} ( a + b )}{p - 1}$ ，恰等于 $a$ 与 $b$ 在 $p$ 进制加法下的进位次数；同余分块取整还常配合埃尔米特（Hermite）恒等式 $\sum_{j = 0}^{m - 1} ⌊ x + j / m ⌋ = ⌊ m x ⌋$ 。例： $n = 100, p = 5$ 时， $v_{5} (100!) = ⌊ 100/5 ⌋ + ⌊ 100/25 ⌋ = 20 + 4 = 24$ ；又 $100 = (400)_{5}$ 的五进制数字和 $s_{5} (100) = 4$ ，由 $(100 - 4) / (5 - 1) = 24$ 亦得 $24$ 。对一般整除或互素条件，一个完整周期内可用容斥计数，末尾不足一周期的部分另算：如不超过 $50$ 且与 $6$ 互素的正整数有 $50 - ⌊ 50/2 ⌋ - ⌊ 50/3 ⌋ + ⌊ 50/6 ⌋ = 50 - 25 - 16 + 8 = 17$ 个。找第 $r$ 个合格数时，应在候选数前后各算一次累计数量。

这里 $p$ 必须为素数， $n, a, b$ 为非负整数， $m$ 为正整数，Hermite 式中的 $x$ 可为任意实数。勒让德和式逐层给每个含 $p^{j}$ 的因子补记一次；写 $n = \sum d_{i} p^{i}$ 后交换有限求和，得 $\sum_{j} ⌊ n / p^{j} ⌋ = \sum_{i} d_{i} (p^{i} - 1) / (p - 1)$ ，即数字和形式。例如 $v_{5} (2025!) = 405 + 81 + 16 + 3 = 505$ 。库默尔公式也可由三个阶乘指数相减得到： $7 + 5$ 的二进制加法有三次进位，而 $(7 12) = 792 = 2^{3} \cdot 99$ ，正好对应 $v_{2} = 3$ 。合数底不能直接套素因数指数的同一和式。

数位、进位和末尾零各有不同编码

十进制整数应按位写成 $n = \sum d_{j} 1 0^{j}$ ，其中首位非零。因为 $10 \equiv 1 (mod 9)$ ，数与数码和模 $9$ 同余，如 $527 \equiv 5 + 2 + 7 \equiv 5 (mod 9)$ 。数位限制遇加法时还要记录进位；末尾零数则是 $min (v_{2} (n), v_{5} (n))$ 。例如 $360 = 2^{3} \cdot 3^{2} \cdot 5$ 只有一个末尾零，不能用位数或数字和代替质因子指数。

方法卡

添项配积与因数配对

添上缺少的常数，把整数方程变成固定整数的因数配对。

完整讲解 · 例题 · 可练 43 题

一、是什么

先认识这些量

因数对 $(u, v)$ 满足 $uv = N$ ，其中 $u, v$ 都是整数。未知数有顺序时，交换两个因数通常得到不同解。

为什么这样做

$x y + x + y = N$ 加 $1$ 后为 $(x + 1) (y + 1) = N + 1$ ，两式等价。但恢复未知数时仍须检查正负和分母。

先看一道例题

例 1：添一

正整数 $x, y$ 满足 $x y + x + y = 11$ ，求全部有序解。

怎么看出来：

加一后乘积为十二。

解：

$(x + 1) (y + 1) = 12$ ，两个因数都至少 $2$ ，故因数对为 $(2, 6), (3, 4), (4, 3), (6, 2)$ 。

答案：

$(1, 5), (2, 3), (3, 2), (5, 1)$ 。

二、什么时候想到它

题目里看到	应该想到
整数方程含乘积与一次项、平方差、单位分数，或给出若干缺一项乘积。	添上缺少的常数，把整数方程变成固定整数的因数配对。
正整数 $x, y$ 满足 $x y + x + y = 11$ ，求全部有序解。	加一后乘积为十二。

三、怎么用

记下原定义域。
配成积或平方差。
列全部符合正负与大小条件的因数对。
恢复未知数并代回。

四、再做一道

例 2：单位分数

正整数 $x \leq y$ 满足 $1/ x + 1/ y = 1/3$ ，求全部解。

怎么看出来：

清分母后添九。

解：

$x y = 3 x + 3 y$ ，故 $(x - 3) (y - 3) = 9$ 。原式迫使 $x, y > 3$ ，有序因数按大小取 $(1, 9), (3, 3)$ 。

答案：

$(4, 12), (6, 6)$ 。

五、容易错在哪

添项前后必须等价，清分母不能保留原来分母为零的值。
正整数条件有时会强迫因数为正，题目允许负数时则须另列负因数。

真题

按这个方法练 · 43 题

收起并返回方法目录

选模、剩余类与局部排除

只看某个模数下的余数，用少量可能性排除整数解或简化大幂。

完整讲解 · 例题 · 可练 72 题

一、是什么

先认识这些量

$a \equiv b (mod m)$ 表示 $m$ 整除 $a - b$ 。模 $m$ 可加减乘；只有与 $m$ 互素的因子才能直接约去。

为什么这样做

整数解必在每个模数下满足相应等式。平方在模 $4$ 下只能余 $0, 1$ ，所以有些方程不必搜索即可排除。

先看一道例题

例 1：平方不可能

整数方程 $x^{2} + y^{2} = 7$ 有解吗？

怎么看出来：

模四右侧余三。

解：

平方模 $4$ 为 $0$ 或 $1$ ，两个平方之和只能余 $0, 1, 2$ ，不能余 $3$ 。

答案：

无整数解。

二、什么时候想到它

题目里看到	应该想到
要求整数解、完全平方、质数或大幂余数；式子在某个小模数下明显简化。	只看某个模数下的余数，用少量可能性排除整数解或简化大幂。
整数方程 $x^{2} + y^{2} = 7$ 有解吗？	模四右侧余三。

三、怎么用

挑选使平方或幂余数很少的模。
列全部可能余数。
排除矛盾，或按幂的周期降指数。
将剩余候选代回，区分必要条件与充分条件。

四、再做一道

例 2：大幂余数

求 $3^{25}$ 除以 $7$ 的余数。

怎么看出来：

先找较短的幂周期。

解：

$3^{3} \equiv - 1 (mod 7)$ ，故 $3^{6} \equiv 1$ 。 $25 = 4 \cdot 6 + 1$ ，所求余数为 $3$ 。

答案：

$3$ 。

五、容易错在哪

模合数下不能随意约因子，例如模六的二没有乘法逆元。
没有模矛盾并不等于原整数方程有解。

真题

按这个方法练 · 72 题

收起并返回方法目录

素因数指数与算术函数

把整除与完全幂条件翻译成每个素因子的指数。

完整讲解 · 例题 · 可练 47 题

一、是什么

先认识这些量

素数 $p$ 在正整数 $N$ 中的最高幂指数记作 $v_{p} (N)$ 。如 $12 = 2^{2} \cdot 3$ ，故 $v_{2} (12) = 2$ 。乘法使指数相加。

为什么这样做

$n!$ 中每个 $p$ 的倍数贡献一次，每个 $p^{2}$ 的倍数再贡献一次，故 $v_{p} (n!) = \sum_{j \geq 1} ⌊ n / p^{j} ⌋$ 。

先看一道例题

例 1：阶乘末零

$15!$ 的十进制末尾有几个零？

怎么看出来：

末零由二和五配对决定。

解：

$v_{5} (15!) = 3$ ， $v_{2} (15!) = 7 + 3 + 1 = 11$ ，故末零数为 $3$ 。

答案：

$3$ 个。

二、什么时候想到它

题目里看到	应该想到
完全幂、阶乘整除、末尾零、因数个数、因数和或欧拉函数成为主要限制。	把整除与完全幂条件翻译成每个素因子的指数。
$15!$ 的十进制末尾有几个零？	末零由二和五配对决定。

三、怎么用

把目标底数分解为素数幂。
分别算每个素因子指数。
按目标幂的重数取整，取最小值。
检查高次素数幂贡献有没有漏算。

四、再做一道

例 2：合数幂整除

最大的非负整数 $k$ ，使 $1 2^{k}$ 整除 $10!$ ，求 $k$ 。

怎么看出来：

十二等于二平方乘三。

解：

$v_{2} (10!) = 5 + 2 + 1 = 8$ ， $v_{3} (10!) = 3 + 1 = 4$ 。故 $k = min (⌊ 8/2 ⌋, 4) = 4$ 。

答案：

$4$ 。

五、容易错在哪

阶乘指数公式的底数必须是素数，不能直接代入十二。
末尾零必须同时检查二和五。

真题

按这个方法练 · 47 题

收起并返回方法目录

公因子归一与欧几里得变形

先提出真正的最大公约数，把剩余两数化成互素参数。

完整讲解 · 例题 · 可练 26 题

一、是什么

先认识这些量

最大公约数是两数最大的正公因子，记为 $g cd (a, b)$ ；最小正公倍数记为 $lcm (a, b)$ 。若 $a = d u, b = d v$ 且 $g cd (u, v) = 1$ ，则最小公倍数为 $d uv$ 。

为什么这样做

提出公因子后，互素部分不能再共享任何素因子，因此乘积中的整除条件容易分离。欧几里得变形 $g cd (a, b) = g cd (a, b - q a)$ 保持公因子集合。

先看一道例题

例 1：和与公约数

正整数 $a \leq b$ ， $a + b = 30$ ，最大公约数为 $6$ ，求全部数对。

怎么看出来：

互素部分之和为五。

解：

$a = 6 u, b = 6 v$ ， $u + v = 5$ 且互素。 $u \leq v$ 给 $(u, v) = (1, 4), (2, 3)$ ，均互素。

答案：

$(6, 24), (12, 18)$ 。

二、什么时候想到它

题目里看到	应该想到
最大公约数、最小公倍数、互素参数或最简分数同时限制未知数。	先提出真正的最大公约数，把剩余两数化成互素参数。
正整数 $a \leq b$ ， $a + b = 30$ ，最大公约数为 $6$ ，求全部数对。	互素部分之和为五。

三、怎么用

设最大公约数为正数 $d$ 。
写成 $d u, d v$ ，保留互素条件。
用最小公倍数或欧几里得变形求参数。
回验公约数恰为所设值。

四、再做一道

例 2：连续线性式

求 $g cd (3 n + 2, 2 n + 1)$ ，其中 $n$ 为非负整数。

怎么看出来：

消去最高项。

解：

两式相减得 $n + 1$ ，再以 $2 n + 1 - 2 (n + 1) = - 1$ ，故公约数只能为 $1$ 。

答案：

$1$ 。

五、容易错在哪

只提出任一公因子并不能保证剩余参数互素。
最小公倍数公式需要使用互素归一后的参数。

真题

按这个方法练 · 26 题

收起并返回方法目录

分块、容斥与累计计数

先数一个完整周期，再数尾段；定位第几项时核对前后累计数。

完整讲解 · 例题 · 可练 24 题

一、是什么

先认识这些量

累计数 $C (N)$ 表示不超过 $N$ 的合格正整数个数。整除条件对最小公倍数取模后重复，就可以分块计数。

为什么这样做

若每个长度 $L$ 的块有 $c$ 个，写 $N = q L + r$ ，则前 $q$ 块贡献 $q c$ ，余下只检查 $r$ 个数。交叠的整除类要用容斥。

先看一道例题

例 1：与六互素

不超过 $20$ 且与 $6$ 互素的正整数有几个？

怎么看出来：

每六个数中余一和五合格。

解：

前三个满块有 $6$ 个； $19, 20$ 中只有 $19$ 合格，共 $7$ 个。

答案：

$7$ 个。

二、什么时候想到它

题目里看到	应该想到
满足整除或互素条件的整数排序、余数类计数，或筛去若干类整数后定位指定项。	先数一个完整周期，再数尾段；定位第几项时核对前后累计数。
不超过 $20$ 且与 $6$ 互素的正整数有几个？	每六个数中余一和五合格。

三、怎么用

确定周期和块端点。
数满块中合格数。
加上尾段，或写累计取整公式。
找第几项时同时验证前一整数的累计数。

四、再做一道

例 2：第十个倍数

将是 $2$ 或 $3$ 的倍数的正整数递增排列，第 $10$ 个是什么？

怎么看出来：

用容斥写累计数。

解：

$C (N) = ⌊ N /2 ⌋ + ⌊ N /3 ⌋ - ⌊ N /6 ⌋$ 。 $C (14) = 9, C (15) = 10$ ，所以第十个为 $15$ 。

答案：

$15$ 。

五、容易错在哪

零余数属于整除类，不能在每块中漏掉。
仅验证候选处累计数等于目标可能落在平台上，还要验证前一整数。

真题

按这个方法练 · 24 题

收起并返回方法目录

排序限界与有限分类

枚举前先证明变量只能落在有限范围内。

完整讲解 · 例题 · 可练 52 题

一、是什么

先认识这些量

排序是暂设 $x \leq y$ 等大小关系以减少重复。上界或下界必须由原条件推出，不能凭试算范围猜测。

为什么这样做

在有界整数区间逐项检查才是穷尽。极值还需给出达到界的合法解。

先看一道例题

例 1：倒数方程

正整数 $x \leq y$ 满足 $1/ x + 1/ y = 1/2$ ，求解。

怎么看出来：

两项各不大于一除以最小数。

解：

$1/2 \leq 2/ x$ 给 $x \leq 4$ ；又 $1/ x < 1/2$ ，故 $x > 2$ 。 $x = 3$ 得 $y = 6$ ， $x = 4$ 得 $y = 4$ 。

答案：

$(3, 6), (4, 4)$ 。

二、什么时候想到它

题目里看到	应该想到
整数未知数很多、要求最小值或最大值，直接枚举没有可证明的停止位置。	枚举前先证明变量只能落在有限范围内。
正整数 $x \leq y$ 满足 $1/ x + 1/ y = 1/2$ ，求解。	两项各不大于一除以最小数。

三、怎么用

保留正性和顺序条件。
由和积或倒数关系限住最小变量。
逐个固定变量检查剩余整数条件。
代回并说明无遗漏及是否恢复顺序。

四、再做一道

例 2：平方差

正整数 $x < y$ 满足 $y^{2} - x^{2} = 15$ ，求解。

怎么看出来：

最大因数已经有限。

解：

$(y - x) (y + x) = 15$ ，正因数对只有 $(1, 15), (3, 5)$ ，解得 $(x, y) = (7, 8), (1, 4)$ 。

答案：

$(1, 4), (7, 8)$ 。

五、容易错在哪

若只在计算机给定范围内搜索，没有范围证明就不能宣称排尽。

真题

按这个方法练 · 52 题

收起并返回方法目录

递推状态与不变量

递推模运算要记录足够长的状态，回到完整旧状态才会重复。

完整讲解 · 例题 · 可练 16 题

一、是什么

先认识这些量

二阶递推中，相邻两项的有序对是一个状态。不变量则是每次递推都保持的式子。

为什么这样做

相同完整状态代入同一规则得到相同后续；单项相等不保证下一项相等。最大公约数也可随递推保持。

先看一道例题

例 1：模二周期

$u_{0} = 0, u_{1} = 1, u_{n + 2} = u_{n + 1} + u_{n}$ ，求模 $2$ 的最小周期。

怎么看出来：

记相邻有序对。

解：

状态依次为 $(0, 1), (1, 1), (1, 0), (0, 1)$ 。此前未回初态，故最小周期为 $3$ 。

答案：

$3$ 。

二、什么时候想到它

题目里看到	应该想到
数列的整除、平方或最大公约数性质依赖相邻几项；重复操作呈有限种模状态。	递推模运算要记录足够长的状态，回到完整旧状态才会重复。
$u_{0} = 0, u_{1} = 1, u_{n + 2} = u_{n + 1} + u_{n}$ ，求模 $2$ 的最小周期。	记相邻有序对。

三、怎么用

写出递推和初态。
取足够多连续项作状态。
逐步计算至完整状态重现，或证明某个量保持。
用归纳证明，不能只凭少量初值。

四、再做一道

例 2：相邻互素

同一递推数列中，证明相邻两项总互素。

怎么看出来：

欧几里得运算把公约数退回上一步。

解：

$g cd (u_{n + 1}, u_{n + 2}) = g cd (u_{n + 1}, u_{n})$ ，逐步退回 $g cd (0, 1) = 1$ 。

答案：

相邻两项最大公约数为 $1$ 。

五、容易错在哪

单项余数第一次重复通常不是周期起点，须比较完整状态。

真题

按这个方法练 · 16 题

收起并返回方法目录

位值展开与数位约束

把数按十进制位值展开，同时保留首位与进位限制。

完整讲解 · 例题 · 可练 21 题

一、是什么

先认识这些量

两位数的十位为 $a$ 、个位为 $b$ 时，数为 $10 a + b$ ，其中 $1 \leq a \leq 9, 0 \leq b \leq 9$ 。数码和是 $a + b$ 。

为什么这样做

调换数位会改变十的权重；减去反序数可消出 $9 (a - b)$ 。模九的数码和只能给必要的整除信息。

先看一道例题

例 1：反序差

两位数的数码和为 $9$ ，比反序数大 $27$ ，求原数。

怎么看出来：

设十位与个位后相减。

解：

$a + b = 9$ ， $9 (a - b) = 27$ ，故 $a - b = 3$ ，解得 $a = 6, b = 3$ ，原数为 $63$ 。

答案：

$63$ 。

二、什么时候想到它

题目里看到	应该想到
数码和、数码积、删位、重复数字、指定数位或进位条件决定整数结构。	把数按十进制位值展开，同时保留首位与进位限制。
两位数的数码和为 $9$ ，比反序数大 $27$ ，求原数。	设十位与个位后相减。

三、怎么用

设各位数码并列范围。
按位值翻译等式。
连同数码和、进位等约束求解。
检查首位非零及所有数码合法。

四、再做一道

例 2：删掉十位

一个两位数减去个位数所得为 $40$ ，数码积为 $12$ ，求原数。

怎么看出来：

减去个位只留下十位权重。

解：

$10 a = 40$ 得 $a = 4$ ，再由 $ab = 12$ 得 $b = 3$ ，两位都合法。

答案：

$43$ 。

五、容易错在哪

首位不能为零，反序后若要求仍为两位数，也要检查新的首位。

真题

按这个方法练 · 21 题

收起并返回方法目录

误区对照

容易误以为

求 $100!$ 十进制表示末尾连续零的个数时，只计算 $100$ 以内 $5$ 的倍数个数 $⌊ 100/5 ⌋ = 20$ ，答 $20$ 个零。

应当这样想

末尾零的个数等于 $min (v_{2} (100!), v_{5} (100!)) = v_{5} (100!)$ 。由勒让德（Legendre）公式，除 $5$ 的倍数外， $25, 50, 75, 100$ 这 $4$ 个 $5^{2}$ 的倍数各额外再贡献一个因子 $5$ ，故 $v_{5} (100!) = ⌊ 100/5 ⌋ + ⌊ 100/25 ⌋ = 20 + 4 = 24$ （或用五进制数字和： $100 = (400)_{5}$ ， $v_{5} (100!) = (100 - 4) / (5 - 1) = 24$ ）。

为什么

每个满足 $p^{k} ∣ m$ 的整数 $m \in [1, n]$ 在 $⌊ n / p ⌋, ⌊ n / p^{2} ⌋, \dots, ⌊ n / p^{k} ⌋$ 中各被统计 $1$ 次，恰好累加其重数 $k$ ；只算 $⌊ n / p ⌋$ 会漏掉所有 $p^{2}, p^{3}, \dots$ 的高次幂重数贡献。

容易误以为

考察斐波那契数列 $F_{1} = 1, F_{2} = 1, F_{n + 2} = F_{n + 1} + F_{n}$ 模 $3$ 的余数序列： $1, 1, 2, 0, 2, 2, 1, 0, 1, 1, \dots$ ，看到 $F_{4} \equiv 0$ 且 $F_{8} \equiv 0 (mod 3)$ ，便误以为模 $3$ 的最小正周期是 $4$ 。

应当这样想

单项余数 $0$ 每 $4$ 步出现一次（因 $F_{n + 4} \equiv 2 F_{n} (mod 3)$ ，在 $F_{4} \equiv 0$ 处反号为 $0$ ），但完整状态对 $(F_{n}, F_{n + 1}) mod 3$ 在 $(F_{5}, F_{6}) \equiv (2, 2) \neq = (1, 1) \equiv (F_{1}, F_{2})$ ，直到 $(F_{9}, F_{10}) \equiv (1, 1)$ 才首次完整复现，故模 $3$ 的最小正周期（Pisano 周期）为 $π (3) = 8$ 。

为什么

二阶递推模 $3$ 在半周期 $T /2 = 4$ 处状态乘以了 $- 1 \equiv 2 (mod 3)$ ，虽然零项位置具有周期 $4$ ，但非零项余数经过 $4$ 步会变为相反数，必须经过 $8$ 步才回到原余数。

概念自测

先想清楚，再确认判断。这些自测只帮助辨清概念，不计入真题做对率。

真题 · 217 道

从易到难排列。圆点表示你在这台设备上的做题情况：绿色做对、黄色部分做对、红色没做出。