Question

对正整数 $n$ ，令 $\tau(n)$ 表示 $n$ 的正整数因数个数，包括 $1$ 和 $n$ 。例如， $\tau(1) = 1$ ， $\tau(6) = 4$ 。定义 $S(n)$ 如下： $S(n) = \tau(1) + \tau(2) + \cdots + \tau(n)\text{。}$ 令 $a$ 表示满足 $n \le 2005$ 且 $S(n)$ 为奇数的正整数个数，令 $b$ 表示满足 $n \le 2005$ 且 $S(n)$ 为偶数的正整数个数。求 $|a - b|$ 。

For positive integers $n,$ let $\tau(n)$ denote the number of positive integer divisors of $n,$ including $1$ and $n.$ For example, $\tau(1) = 1$ and $\tau(6) = 4.$ Define $S(n)$ by $S(n) = \tau(1) + \tau(2) + \cdots + \tau(n).$ Let $a$ denote the number of positive integers $n \le 2005$ with $S(n)$ odd, and let $b$ denote the number of positive integers $n \le 2005$ with $S(n)$ even. Find $|a - b|.$

答案

答案：25

知识点：奇偶性完全平方数因数个数

难度评级：2760

小提示：

$\tau(n)$ 为奇数当且仅当 $n$ 是完全平方数，所以 $S(n)$ 只会在平方数处改变奇偶性

$\tau(n)$ is odd exactly when $n$ is a perfect square, so $S(n)$ changes parity only at squares

大提示：

$S(n)$ 为奇数当且仅当 $\lfloor\sqrt{n}\rfloor$ 为奇数；在相邻平方数之间逐块统计 $n \le 2005$

$S(n)$ is odd exactly when $\lfloor\sqrt{n}\rfloor$ is odd; count $n \le 2005$ block by block between consecutive squares

解答：

$n$ 的因数可以配成 $d$ 和 $\frac{n}{d}$ ，两两一对，所以 $\tau(n)$ 为奇数当且仅当 $n$ 是完全平方数。因此 $S(n)$ 恰好在平方数处改变奇偶性，也就是说 $S(n)$ 为奇数，当且仅当不超过 $n$ 的平方数个数，即 $\lfloor\sqrt{n}\rfloor$ 为奇数。

对每个 $k$ ，满足 $\lfloor\sqrt{n}\rfloor = k$ 的整数 $n$ 有 $2k + 1$ 个，即 $k^2 \le n \le k^2 + 2k$ 。因为 $44^2 = 1936$ $\le 2005$ $\lt 2025 = 45^2$ ，奇数 $k = 1, 3, \ldots, 43$ 的完整区块都在范围内，所以 $\begin{aligned} a &= \sum_{k \text{ 奇数},\, k \le 43} (2k + 1) \\ &= 2(1 + 3 + \cdots + 43) + 22 \\ &= 2 \cdot 484 + 22 \\ &= 990 \end{aligned}\text{。}$

于是 $b = 2005 - 990 = 1015$ ，且 $|a - b| = 25$ 。

Divisors of $n$ pair up as $d$ and $\frac{n}{d},$ so $\tau(n)$ is odd exactly when $n$ is a perfect square. Hence $S(n)$ changes parity exactly at the squares, which means $S(n)$ is odd exactly when the number of squares up to $n,$ namely $\lfloor\sqrt{n}\rfloor,$ is odd.

For each $k,$ there are $2k + 1$ integers $n$ with $\lfloor\sqrt{n}\rfloor = k,$ namely $k^2 \le n \le k^2 + 2k.$ Since $44^2 = 1936$ $\le 2005$ $\lt 2025 = 45^2,$ the odd values $k = 1, 3, \ldots, 43$ all have their full blocks within range, so $\begin{aligned} a &= \sum_{k \text{ odd},\, k \le 43} (2k + 1) \\ &= 2(1 + 3 + \cdots + 43) + 22 \\ &= 2 \cdot 484 + 22 \\ &= 990. \end{aligned}$

Then $b = 2005 - 990 = 1015,$ and $|a - b| = 25.$

2005 AIME I 第 12 题

答案：25

难度评级：2760

小提示：

大提示：

解答：

其他年份的第 12 题