← Reading List
🧮 奥数题

奥数每日两题 2026-07-24:LCM 与 GCD 反推整数 / 子集链计数与取模

奥数题数学AMC10AMC12数论组合

今日学段:数论 + 组合(AMC 10/12 难度)

题目来源:AMC 12A 竞赛真题(经 AI-MO 官方题库整理,题面链接指向 AoPS Wiki)


【{seg1}】{p1_title}

难度: ⭐⭐⭐(高中竞赛数论基础题,考查质因数分解与 LCM/GCD 的相互约束)

题目来源: 2022 AMC 12A Problem 4

知识点: 质因数分解 · 最小公倍数与最大公约数

题目:

设正整数 $n$ 与 $18$ 的最小公倍数为 $180$,且 $n$ 与 $45$ 的最大公约数为 $15$。求 $n$ 的各位数字之和。


解题过程

第一步:把所有数字写成质因数分解形式。

\[18 = 2^1 \cdot 3^2, \quad 180 = 2^2 \cdot 3^2 \cdot 5^1, \quad 45 = 3^2 \cdot 5^1, \quad 15 = 3^1 \cdot 5^1.\]

设 $n = 2^a \cdot 3^b \cdot 5^c \cdot (\text{其他质因子})$。

第二步:用 LCM 条件 $\operatorname{lcm}(n,18)=180$ 约束各指数。

对每个质因子,LCM 取两数指数的最大值:

  • 质因子 $2$:$\max(a,1)=2 \Rightarrow a=2$。
  • 质因子 $3$:$\max(b,2)=2 \Rightarrow b\le 2$。
  • 质因子 $5$:$\max(c,0)=1 \Rightarrow c=1$。
  • $180$ 不含其他质因子,故 $n$ 也不能含其他质因子。

第三步:用 GCD 条件 $\gcd(n,45)=15$ 确定 $b$。

GCD 取两数指数的最小值:

  • 质因子 $3$:$\min(b,2)=1 \Rightarrow b=1$。
  • 质因子 $5$:$\min(c,1)=1$,与 $c=1$ 一致。

第四步:确定 $n$ 并求数字之和。

\[n = 2^2 \cdot 3^1 \cdot 5^1 = 4 \cdot 3 \cdot 5 = 60.\]

各位数字之和为 $6 + 0 = \boxed{6}$。


常见错误

  • 只用 LCM 条件而忽略 GCD,误以为 $b$ 可取 $0,1,2$ 而得出多个答案;实际上 GCD 把 $b$ 唯一锁定为 $1$。
  • 把 LCM 的「取最大值」和 GCD 的「取最小值」记反,导致指数方向错误。
  • 忘记检查「$180$ 不含其他质因子」这一隐含约束,误加入多余质因子。

知识背景

对任意两个正整数,若写成质因数分解 $x=\prod p_i^{e_i}$、$y=\prod p_i^{f_i}$,则 $\gcd$ 对每个质因子取指数最小值、$\operatorname{lcm}$ 取最大值,并满足恒等式 $\gcd(x,y)\cdot\operatorname{lcm}(x,y)=x\cdot y$。这类「已知 LCM/GCD 反推原数」的题目,核心技巧就是逐个质因子分别列出 $\max$ / $\min$ 约束,把一个整数问题拆成若干独立的指数不等式,是 AMC 数论部分的高频套路。


【{seg2}】{p2_title}

难度: ⭐⭐⭐⭐(高中竞赛压轴级组合题,需要「按元素独立计数」的转化思想)

题目来源: 2023 AMC 12A Problem 24

知识点: 子集链计数 · 独立计数原理 · 幂的取模

题目:

设 $K$ 为满足下列条件的序列 $A_1, A_2, \dots, A_n$ 的个数:$n$ 是不超过 $10$ 的正整数,每个 $A_i$ 都是 ${1,2,3,\dots,10}$ 的子集,且对 $2\le i\le n$ 都有 $A_{i-1}\subseteq A_i$。例如 ${},\ {5,7},\ {2,5,7},\ {2,5,7},\ {2,5,6,7,9}$ 就是一个这样的序列(此时 $n=5$)。求 $K$ 除以 $10$ 的余数。


解题过程

第一步:固定长度 $n$,按元素独立计数。

固定链长为 $n$。考虑集合 ${1,\dots,10}$ 中的某个元素 $x$。由于 $A_1\subseteq A_2\subseteq\cdots\subseteq A_n$,一旦 $x$ 进入某个 $A_i$,之后就一直存在。于是 $x$ 的「命运」完全由它第一次出现的位置决定:可以在第 $1,2,\dots,n$ 个集合中首次出现,也可以自始至终都不出现——共 $n+1$ 种选择。

第二步:$10$ 个元素相互独立。

每个元素各自有 $n+1$ 种选择,且互不影响,故长度恰为 $n$ 的链共有

\[(n+1)^{10}\]

条。

第三步:对 $n=1$ 到 $10$ 求和。

\[K = \sum_{n=1}^{10} (n+1)^{10} = \sum_{k=2}^{11} k^{10}.\]

第四步:逐项取个位(模 $10$)。

只需每个 $k^{10}$ 的个位:

$k$ 2 3 4 5 6 7 8 9 10 11
$k^{10}\bmod 10$ 4 9 6 5 6 9 4 1 0 1

相加:$4+9+6+5+6+9+4+1+0+1 = 45$。

\[K \equiv 45 \equiv \boxed{5} \pmod{10}.\]

常见错误

  • 试图直接枚举所有链,陷入 $n$ 与集合的双重组合爆炸;关键是转成「每个元素独立选首次出现位置」。
  • 漏掉「元素从不出现」这一种情况,把 $n+1$ 误算成 $n$。
  • 计算 $k^{10}\bmod 10$ 时忘记利用个位数的循环周期,导致算错某一项。

知识背景

「链计数」是组合中的经典模型:一条 $A_1\subseteq\cdots\subseteq A_n$ 的子集链,等价于给每个元素分配一个「加入时刻」$\in{1,\dots,n,\text{never}}$。这种「把整体结构拆到每个元素上独立决策」的思想,与「多重集排列」「隔板法」同属组合计数的核心技巧。最后一步的幂取模则依赖个位数的循环节($2,3,7,8$ 周期为 $4$;$4,9$ 周期为 $2$;$0,1,5,6$ 恒定),是数论与组合结合的常见收尾。

评论