Question

设 $\mathcal{S}$ 为所有通常数字写法末三位是 $256$ 的完全平方数的集合。设 $\mathcal{T}$ 为所有形如 $\frac{x - 256}{1000}$ 的数的集合，其中 $x$ 属于 $\mathcal{S}$ 。换句话说， $\mathcal{T}$ 是把 $\mathcal{S}$ 中每个数的末三位截去后得到的数的集合。求 $\mathcal{T}$ 中第 $10$ 小的元素除以 $1000$ 的余数。

Let $\mathcal{S}$ be the set of all perfect squares whose rightmost three digits in base $10$ are $256.$ Let $\mathcal{T}$ be the set of all numbers of the form $\frac{x - 256}{1000},$ where $x$ is in $\mathcal{S}.$ In other words, $\mathcal{T}$ is the set of numbers that result when the last three digits of each number in $\mathcal{S}$ are truncated. Find the remainder when the tenth smallest element of $\mathcal{T}$ is divided by $1000.$

答案

答案：170

知识点：模运算中国剩余定理平方差

难度评级：2840

解答：

一个平方数 $n^2$ 末三位为 $256$ ，当且仅当 $1000 \mid n^2 - 256$ $= (n - 16)(n + 16)$ 。模 $8$ 时， $n^2 \equiv 0 \pmod 8$ ，迫使 $4 \mid n$ 。模 $125$ 时，两个因子 $n \pm 16$ 相差 $32$ ，所以 $5$ 至多整除其中一个；因此 $125$ 必须整除某一个因子，即 $n \equiv \pm 16 \pmod{125}$ 。由于 $16$ 是 $4$ 的倍数，两条件合并为 $n \equiv \pm 16 \pmod{500}$ 。

所以 $\mathcal{S}$ 由形如 $(500m \pm 16)^2$ 的数构成，其平方根按递增顺序为 $16$ 、 $484$ 、 $516$ 、 $984$ 、 $1016, \ldots$ 。 $\mathcal{S}$ 中第十小的元素是 $(500 \cdot 5 - 16)^2 = 2484^2$ 。

对应的 $\mathcal{T}$ 中元素为 $\frac{2484^2 - 256}{1000} = \frac{2468 \cdot 2500}{1000} = 6170$ ，除以 $1000$ 的余数是 $170$ 。

A square $n^2$ ends in $256$ exactly when $1000 \mid n^2 - 256$ $= (n - 16)(n + 16).$ Modulo $8:$ $n^2 \equiv 0 \pmod 8$ forces $4 \mid n.$ Modulo $125:$ the factors $n \pm 16$ differ by $32,$ so $5$ divides at most one of them, and hence $125$ must divide a single factor: $n \equiv \pm 16 \pmod{125}.$ Because $16$ is a multiple of $4,$ the two conditions combine to $n \equiv \pm 16 \pmod{500}.$

So $\mathcal{S}$ consists of the numbers $(500m \pm 16)^2,$ whose square roots in increasing order are $16,$ $484,$ $516,$ $984,$ $1016, \ldots.$ The tenth smallest element of $\mathcal{S}$ is $(500 \cdot 5 - 16)^2 = 2484^2.$

The corresponding element of $\mathcal{T}$ is $\frac{2484^2 - 256}{1000} = \frac{2468 \cdot 2500}{1000} = 6170,$ whose remainder upon division by $1000$ is $170.$

2012 AIME I 第 10 题

答案：170

难度评级：2840

解答：

其他年份的第 10 题