Question

求不超过 $100$ 的整数中，有多少个可以写成 $a + b + ab$ ，其中 $a$ 和 $b$ 是两个不同的正整数。

Find the number of integers less than or equal to $100$ that are equal to $a + b + ab$ for some choice of distinct positive integers $a$ and $b.$

答案

答案：70

知识点：西蒙最爱的因式分解技巧补集计数质数

难度评级：2300

小提示：

两边加 $1$ ： $a + b + ab + 1 = (a+1)(b+1)$

Add $1$ to both sides: $a + b + ab + 1 = (a+1)(b+1)$

大提示：

因此 $n$ 可行当且仅当 $n + 1$ 是两个不同因数的乘积，且每个因数至少为 $2$ ；从 $2$ 到 $101$ 中去掉质数和质数的平方

So $n$ works exactly when $n + 1$ is a product of two distinct factors, each at least $2;$ remove the primes and the squares of primes from $2$ through $101$

解答：

因为 $a + b + ab = (a+1)(b+1) - 1$ ，整数 $n$ 可表示当且仅当 $n + 1 = xy$ ，其中 $x = a + 1$ 和 $y = b + 1$ 是不同整数且都至少为 $2$ 。所以我们统计 $n + 1$ 在集合 $\{2, 3, \ldots, 101\}$ 中且能如此分解的情形。

质数不能分解成两个都至少为 $2$ 的因数；质数平方 $p^2$ 只能这样分解为 $p \cdot p$ ，但这不允许。其余每个合数 $M$ 都可行：若 $p$ 是它的最小质因数，则 $M = p \cdot \frac{M}{p}$ ，且有 $\frac{M}{p} \gt p$ ，因为 $M \gt p^2$ 。在 $\{2, \ldots, 101\}$ 中有 $26$ 个质数，其中 $25$ 个小于 $100$ ，另一个是 $101$ ；另有 $4$ 个质数平方，即 $4$ 、 $9$ 、 $25$ 、 $49$ 。

个数为 $100 - 26 - 4 = 70$ 。

Since $a + b + ab = (a+1)(b+1) - 1,$ an integer $n$ is representable exactly when $n + 1 = xy$ for distinct integers $x = a + 1$ and $y = b + 1$ that are each at least $2.$ So we count integers $n + 1$ in $\{2, 3, \ldots, 101\}$ that admit such a factorization.

A prime has no factorization into two factors that are both at least $2,$ and the square of a prime $p^2$ factors that way only as $p \cdot p,$ which is not allowed. Every other composite $M$ works: if $p$ is its smallest prime factor, then $M = p \cdot \frac{M}{p}$ with $\frac{M}{p} \gt p$ since $M \gt p^2.$ In $\{2, \ldots, 101\}$ there are $26$ primes (the $25$ primes below $100,$ together with $101$ ) and $4$ prime squares ( $4,$ $9,$ $25,$ $49$ ).

The count is $100 - 26 - 4 = 70.$

2026 AIME I 第 4 题

答案：70

难度评级：2300

小提示：

大提示：

解答：

其他年份的第 4 题