整除与因数

考什么 · What it tests

需要先会 · Prerequisites

• 质数与合数 / Primes and composites
• 整除规则（$2/3/5/9$ 等） / Divisibility rules (2/3/5/9, etc.)
• 指数记法 / Exponent notation

常见套路 · Common moves

1. 一切先质因数分解：把数拆成 $p^a q^b\cdots$，因数个数就是 $(a+1)(b+1)\cdots$，GCD/LCM 也直接从指数取小/取大——数论题的万能第一步。

   Prime-factorize everything first: write the number as $p^a q^b\cdots$, then the divisor count is $(a+1)(b+1)\cdots$, and GCD/LCM come from taking the smaller/larger exponents — the universal first step in number theory.
2. 整除规则速判：3 和 9 看各位数字之和，4 看末两位，8 看末三位，11 看奇偶位数字之差。

   Quick divisibility checks: for 3 and 9 use the digit sum, for 4 the last two digits, for 8 the last three, for 11 the difference of odd- and even-position digits.
3. 完全平方数的因数个数是奇数：因数本来成对出现，只有平方数因为 $\sqrt{n}$ 自己配自己，个数才是奇数。

   A perfect square has an odd number of divisors: divisors normally pair up, but a square is the only case where $\sqrt{n}$ pairs with itself, making the count odd.

易错点 · Common pitfalls

• GCD 和 LCM 记反：GCD 取质因数指数的最小值，LCM 取最大值——问「最小公倍数」却取了小指数是高频错。

  Swapping GCD and LCM: GCD takes the smaller exponent of each prime, LCM the larger — grabbing the small one for the "least common multiple" is a frequent slip.
• 因数个数公式忘了「加 1」：$2^3$ 有 3+1=4 个因数（$1,2,4,8$），不是 3 个。

  Forgetting the "+1" in the divisor-count formula: $2^3$ has 3+1=4 divisors ($1,2,4,8$), not 3.