Question

设 $S$ 是所有有理数 $r$ 组成的集合，其中 $0\lt r\lt1$ ，且具有如下循环小数表示： $0.abcabcabc\ldots=0.\overline{abc}\text{，}$ 这里的数字 $a$ 、 $b$ 和 $c$ 不一定互不相同。将 $S$ 中的元素都写成最简分数时，一共需要多少个不同的分子？

Let $S$ be the set of all rational numbers $r,$ $0\lt r\lt1,$ that have a repeating decimal expansion in the form $0.abcabcabc\ldots=0.\overline{abc},$ where the digits $a,$ $b,$ and $c$ are not necessarily distinct. To write the elements of $S$ as fractions in lowest terms, how many different numerators are required?

答案

答案：660

知识点：循环小数最大公约数欧拉函数

难度评级：2320

小提示：

每个元素都形如 $\frac{N}{999}$ ，其约分后的分母一定整除 $999=3^3\cdot37$

Every element has the form $\frac{N}{999}$ , and its reduced denominator must divide $999=3^3\cdot37$

大提示：

先数出与 $999$ 互质的分子，再检查还有哪些 $3$ 的倍数能以 $37$ 为分母

Count numerators coprime to $999$ , then check which additional multiples of $3$ can occur with denominator $37$

解答：

每个元素都可写成 $\frac{N}{999}$ ，其中 $1\leq N\leq998$ 。若 $a$ 与 $999$ 互质，它就会作为分母为 $999$ 的最简分数的分子出现，共有 $\varphi(999)=648$ 个。若 $a$ 能被 $3$ 整除但不能被 $37$ 整除，则它只有在约分后的分母为 $37$ 时才可能与分母互质；这又加入了 $12$ 个 $3$ 的倍数，它们都小于 $37$ 。若分子能被 $37$ 整除，则分母必须既整除 $27$ 又大于该分子，这是不可能的。因此没有其他分子，所求总数为 $648+12=660$ 。

Every element is $\frac{N}{999}$ for $1\leq N\leq998.$ Any $a$ coprime to $999$ occurs as a reduced numerator with denominator $999,$ giving $\varphi(999)=648$ values. If $a$ is divisible by $3$ but not $37,$ it can be coprime to a reduced denominator only when that denominator is $37;$ this adds the $12$ multiples of $3$ below $37.$ A numerator divisible by $37$ would need a denominator dividing $27$ and larger than it, so no further values occur. Therefore the total is $648+12=660.$

1992 AIME 第 5 题

答案：660

难度评级：2320

小提示：

大提示：

解答：

其他年份的第 5 题