Question

设 $S_i$ 为所有满足 $100i \le n \lt 100(i + 1)$ 的整数 $n$ 组成的集合。例如， $S_4$ 是集合 $\{400, 401, 402, \ldots, 499\}$ 。在 $S_0, S_1, S_2, \ldots, S_{999}$ 这些集合中，有多少个集合不含完全平方数？

Let $S_i$ be the set of all integers $n$ such that $100i \le n \lt 100(i + 1).$ For example, $S_4$ is the set $\{400, 401, 402, \ldots, 499\}.$ How many of the sets $S_0, S_1, S_2, \ldots, S_{999}$ do not contain a perfect square?

答案

答案：708

知识点：完全平方数区间内整数计数

难度评级：2510

解答：

当 $a \le 49$ 时，相邻平方数 $a^2$ 与 $(a + 1)^2$ 相差 $2a + 1 \le 99$ ，所以从 $1^2$ 到 $50^2 = 2500$ 的平方数不会跳过任何一个百数段：每个集合 $S_0, S_1, \ldots, S_{25}$ 都含有完全平方数。对 $a \ge 50$ ，间距 $2a + 1 \ge 101$ 超过 $100$ ，所以集合 $S_{26}, \ldots, S_{999}$ 中每个至多含一个平方数。

涉及的最大数为 $99999$ ，且 $316^2 = 99856 \le 99999 \lt 317^2$ 。因此落在 $S_{26}, \ldots, S_{999}$ 中的平方数是 $51^2, 52^2, \ldots, 316^2$ ，共 $266$ 个平方数，占据这 $974$ 个集合中的 $266$ 个不同集合。

因此有 $974 - 266 = 708$ 个集合不含完全平方数。

Consecutive squares $a^2$ and $(a + 1)^2$ differ by $2a + 1 \le 99$ for $a \le 49,$ so the squares from $1^2$ to $50^2 = 2500$ never skip a hundred-block: every set $S_0, S_1, \ldots, S_{25}$ contains a perfect square. For $a \ge 50$ the gap $2a + 1 \ge 101$ exceeds $100,$ so each of the sets $S_{26}, \ldots, S_{999}$ contains at most one square.

The largest number involved is $99999,$ and $316^2 = 99856 \le 99999 \lt 317^2.$ So the squares landing in $S_{26}, \ldots, S_{999}$ are $51^2, 52^2, \ldots, 316^2$ — that is, $266$ squares occupying $266$ distinct sets out of those $974.$

Therefore $974 - 266 = 708$ sets contain no perfect square.

2008 AIME I 第 7 题

答案：708

难度评级：2510

解答：

其他年份的第 7 题