← Reading List
🧮 奥数题

奥数每日两题 2026-11-10:GCD与LCM的有序对 / 圆排列中的相邻限制

奥数题数学AMC10AMC12数论组合

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

题目来源:AMC 10 竞赛真题(通过 mathmastery 题库抓取)


【数论】GCD 与 LCM 的有序正整数对

难度: ⭐⭐⭐(高中竞赛 · 数论基础)

题目来源: AMC 10 · GCD and LCM

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

题目:

满足条件的有序正整数对 $(a,b)$ 共有多少组,使得 $\gcd(a,b)=6$ 且 $\operatorname{lcm}(a,b)=540$?

  • (A) $2$
  • (B) $4$
  • (C) $6$
  • (D) $8$
  • (E) $10$

解题过程

设 $a=6s,\ b=6t$,其中 $s,t$ 为正整数且 $\gcd(s,t)=1$。

由最小公倍数公式:

\[\operatorname{lcm}(a,b)= rac{ab}{\gcd(a,b)}= rac{36st}{6}=6st\]

已知 $\operatorname{lcm}(a,b)=540$,故

\[6st=540 \quad\Rightarrow\quad st=90\]

对 $90$ 做质因数分解:

\[90 = 2 imes 3^2 imes 5\]

我们需要在 $st=90$ 的条件下,找出满足 $\gcd(s,t)=1$ 的无序对 $(s,t)$(之后再乘 $2$ 得到有序对)。

枚举 $90$ 的因数对(不妨设 $s\le t$):

$(s,t)$ $\gcd(s,t)$ 是否互质
$(1,90)$ $1$ ✓
$(2,45)$ $1$ ✓
$(3,30)$ $3$ ✗
$(5,18)$ $1$ ✓
$(6,15)$ $3$ ✗
$(9,10)$ $1$ ✓

互质的无序对共有 $4$ 组:$(1,90),(2,45),(5,18),(9,10)$。

每一组无序对对应 $2$ 个有序对(交换 $s,t$),因此有序对总数为:

\[4 imes 2 = 8\]

答案:(D) $8$


常见错误

  • 忘记”有序对”需乘 $2$,只数出 $4$ 组无序对而误选 (B)。
  • 误以为 $(3,30)$、$(6,15)$ 也互质——其实它们有公因子 $3$,必须剔除。
  • 直接令 $a\cdot b=6 imes540$ 后乱枚举,没有先提取公因子 $6$,导致重复或遗漏。

知识背景

对于任意正整数 $a,b$,恒有 $\gcd(a,b)\cdot\operatorname{lcm}(a,b)=ab$。当二者乘积已知后,可设 $a=gx,\ b=gy$(其中 $g=\gcd(a,b),\ \gcd(x,y)=1$),则 $\operatorname{lcm}(a,b)=gxy$。于是问题转化为”在 $xy=N$ 的约束下,统计互质因子的配对方式”。这是 AMC 数论中极经典的一类题,核心是质因数分解 + 互质条件。


【组合】圆排列中的相邻限制

难度: ⭐⭐⭐(高中竞赛 · 排列组合)

题目来源: AMC 10 · Circular Permutations

知识点: 圆排列 · 补集思想 · 捆绑法

题目:

$6$ 个人站成一个圆圈,其中指定的两个人不能相邻。共有多少种站法?

  • (A) $48$
  • (B) $60$
  • (C) $72$
  • (D) $72$
  • (E) $96$

解题过程

总排列数(无限制):

$n$ 个人围成一圈,圆排列数为 $(n-1)!$。因此 $6$ 人无限制站法:

\[(6-1)! = 5! = 120\]

违反条件的站法(两人相邻):

用捆绑法,把这两个必须相邻的人看作一个整体(一个”块”)。此时相当于 $5$ 个对象(块 + 其余 $4$ 人)围成一圈:

\[(5-1)! = 4! = 24\]

块内部两人可以左右互换,有 $2$ 种排法。故相邻站法数为:

\[4! imes 2 = 24 imes 2 = 48\]

满足条件的站法(补集):

\[120 - 48 = 72\]

答案:(C) $72$


常见错误

  • 用直线排列 $6!$ 而非圆排列 $5!$ 作为总数,导致后续全部算错。
  • 忘记块内部两人的 $2$ 种内部排列,得到 $120-24=96$ 误选 (E)。
  • 圆排列中”旋转视为相同”,但”翻转(镜像)是否相同”需注意:本题默认旋转等价、镜像不等价(一般圆排列标准定义),故总数为 $5!$ 而非 $5!/2$。

知识背景

圆排列与直线排列的关键区别在于旋转等价:固定一人位置后,其余 $n-1$ 人相对排列,故总数为 $(n-1)!$。处理”某些元素不能相邻”的约束时,补集 + 捆绑法是最常用套路:先算总数,再算”最坏情况”(指定元素相邻,捆绑成块)并扣除。这一思想在 AMC 10/12 的组合题中反复出现。

评论