Question

设 $S$ 为整数有序对 $(a, b)$ 的个数，其中 $1 \le a \le 100$ 、 $b \ge 0$ ，并且多项式 $x^2 + ax + b$ 可以分解为两个（不一定不同的）整系数一次因式的乘积。求 $S$ 除以 $1000$ 的余数。

Let $S$ be the number of ordered pairs of integers $(a, b),$ with $1 \le a \le 100$ and $b \ge 0,$ such that the polynomial $x^2 + ax + b$ can be factored into the product of two (not necessarily distinct) linear factors with integer coefficients. Find the remainder when $S$ is divided by $1000.$

答案

答案：600

知识点：二次方程完全平方数奇偶性

难度评级：2260

解答：

该多项式分解为整系数一次因式，恰好等价于它的根是整数，也就是判别式 $a^2 - 4b$ 等于某个整数 $c \ge 0$ 的平方 $c^2$ 。给定 $a$ 时，这样的 $b \ge 0$ 存在，当且仅当 $4b = a^2 - c^2 = (a-c)(a+c)$ ，其中 $c$ 满足 $0 \le c \le a$ 且 $c \equiv a \pmod 2$ ，不同的 $c$ 给出不同的 $b = \frac{a^2 - c^2}{4}$ 。

当 $a$ 为奇数时，有效的 $c$ 是 $1, 3, \ldots, a$ ，共有 $\frac{a+1}{2}$ 个；当 $a$ 为偶数时，有效值是 $0, 2, \ldots, a$ ，共有 $\frac{a}{2} + 1$ 个。

对 $a = 1, \ldots, 100$ 求和：奇数 $a$ 贡献 $1 + 2 + \cdots + 50 = 1275$ ，偶数 $a$ 贡献 $2 + 3 + \cdots + 51 = 1325$ 。因此 $S = 2600$ ，余数为 $600$ 。

The polynomial factors into integer linear factors exactly when its roots are integers, that is, when the discriminant $a^2 - 4b$ equals $c^2$ for some integer $c \ge 0.$ Given $a,$ such a $b \ge 0$ exists exactly when $4b = a^2 - c^2 = (a-c)(a+c)$ for some $c$ with $0 \le c \le a$ and $c \equiv a \pmod 2,$ and distinct such $c$ give distinct values $b = \frac{a^2 - c^2}{4}.$

For odd $a$ the valid $c$ are $1, 3, \ldots, a,$ which is $\frac{a+1}{2}$ choices; for even $a$ they are $0, 2, \ldots, a,$ which is $\frac{a}{2} + 1$ choices.

Summing over $a = 1, \ldots, 100:$ the odd $a$ contribute $1 + 2 + \cdots + 50 = 1275,$ and the even $a$ contribute $2 + 3 + \cdots + 51 = 1325.$ Thus $S = 2600,$ and the remainder is $600.$

2018 AIME I 第 1 题

答案：600

难度评级：2260

解答：

其他年份的第 1 题