Question

对每个正整数 $p$ ，令 $b(p)$ 表示唯一的正整数 $k$ 使得 $|k - \sqrt{p}| \lt \frac{1}{2}$ 。例如， $b(6) = 2$ ，且 $b(23) = 5$ 。若 $S = \sum_{p=1}^{2007} b(p)$ ，求 $S$ 除以 $1000$ 的余数。

For each positive integer $p,$ let $b(p)$ denote the unique positive integer $k$ such that $|k - \sqrt{p}| \lt \frac{1}{2}.$ For example, $b(6) = 2$ and $b(23) = 5.$ If $S = \sum_{p=1}^{2007} b(p),$ find the remainder when $S$ is divided by $1000.$

答案

答案：955

知识点：取整函数前n项平方和区间内整数计数

难度评级：2610

小提示：

$b(p) = k$ 当且仅当 $k^2 - k + 1 \le p \le k^2 + k$ ，这是含有 $2k$ 个 $p$ 值的一段

$b(p) = k$ exactly when $k^2 - k + 1 \le p \le k^2 + k,$ a block of $2k$ values of $p$

大提示：

对 $k \le 44$ 的完整区段覆盖到 $p \le 1980$ ；剩下的每个 $p$ ，直到 $2007$ ，都满足 $b(p) = 45$

Complete blocks for $k \le 44$ cover $p \le 1980;$ every remaining $p$ up to $2007$ has $b(p) = 45$

解答：

对正整数 $k$ ，条件 $|k - \sqrt{p}| \lt \frac{1}{2}$ 意味着 $\left(k - \frac{1}{2}\right)^2 \lt p \lt \left(k + \frac{1}{2}\right)^2$ ，对整数 $p$ 而言，这恰好等价于 $k^2 - k + 1 \le p \le k^2 + k$ 。因此，满足 $b(p) = k$ 的取值范围含有 $2k$ 个 $p$ 。

因为 $44^2 + 44 = 1980$ ，区段 $k = 1, \ldots, 44$ 恰好覆盖所有 $p \le 1980$ ，贡献 $\begin{aligned} \sum_{k=1}^{44} k \cdot 2k &= 2 \cdot \frac{44 \cdot 45 \cdot 89}{6} \\ &= 58740 \end{aligned}\text{。}$ 剩下的 $27$ 个值 $p = 1981, \ldots, 2007$ 都有 $b(p) = 45$ ，又增加 $27 \cdot 45 = 1215$ 。

因此 $S = 58740 + 1215 = 59955$ ，余数为 $955$ 。

For a positive integer $k,$ the condition $|k - \sqrt{p}| \lt \frac{1}{2}$ means $\left(k - \frac{1}{2}\right)^2 \lt p \lt \left(k + \frac{1}{2}\right)^2,$ which for integers $p$ is exactly $k^2 - k + 1 \le p \le k^2 + k.$ So $b(p) = k$ for precisely $2k$ values of $p.$

Since $44^2 + 44 = 1980,$ the blocks $k = 1, \ldots, 44$ exactly cover $p \le 1980$ and contribute $\begin{aligned} \sum_{k=1}^{44} k \cdot 2k &= 2 \cdot \frac{44 \cdot 45 \cdot 89}{6} \\ &= 58740. \end{aligned}$ The remaining $27$ values $p = 1981, \ldots, 2007$ each have $b(p) = 45,$ adding $27 \cdot 45 = 1215.$

Thus $S = 58740 + 1215 = 59955,$ and the remainder is $955.$

2007 AIME I 第 11 题

答案：955

难度评级：2610

小提示：

大提示：

解答：

其他年份的第 11 题