Question

对正整数 $p$ ，如果正整数 $n$ 与 $p$ 的任意倍数之差的绝对值都大于 $2$ ，就称 $n$ 为 $p$ -安全数。例如， $10$ -安全数的集合为 $\{3, 4, 5, 6, 7, 13, 14, 15$ 、 $16, 17, 23, \ldots\}$ 。求不超过 $10{,}000$ 且同时为 $7$ -安全数、 $11$ -安全数和 $13$ -安全数的正整数个数。

For a positive integer $p,$ define the positive integer $n$ to be $p$ -safe if $n$ differs in absolute value by more than $2$ from all multiples of $p.$ For example, the set of $10$ -safe numbers is $\{3, 4, 5, 6, 7, 13, 14, 15,$ $16, 17, 23, \ldots\}.$ Find the number of positive integers less than or equal to $10{,}000$ which are simultaneously $7$ -safe, $11$ -safe, and $13$ -safe.

答案

答案：958

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

难度评级：2920

解答：

是否为 $p$ -安全数只取决于 $n \bmod p$ ：它要求 $3 \le n \bmod p \le p - 3$ 。模 $7$ 有 $2$ 个允许的余数，模 $11$ 有 $6$ 个，模 $13$ 有 $8$ 个。由于 $7 \cdot 11 \cdot 13 = 1001$ ，由中国剩余定理，模 $1001$ 恰好有 $2 \cdot 6 \cdot 8 = 96$ 个安全余数，所以每个连续 $1001$ 个整数块含有 $96$ 个安全数。

整数 $1$ 到 $10010$ 构成十个这样的块，含有 $960$ 个安全数。还需要去掉 $10001, \ldots, 10010$ 中的安全数。它们模 $7$ 的余数依次为 $5, 6, 0, 1, 2, 3, 4, 5, 6, 0$ ，所以只有 $10006$ 和 $10007$ 是 $7$ -安全的；它们也都是 $11$ -安全的（余数为 $7$ 和 $8$ ）且是 $13$ -安全的（余数为 $9$ 和 $10$ ）。

因此计数为 $960 - 2 = 958$ 。

Being $p$ -safe depends only on $n \bmod p:$ it requires $3 \le n \bmod p \le p - 3.$ That allows $2$ residues modulo $7,$ $6$ residues modulo $11,$ and $8$ residues modulo $13.$ Since $7 \cdot 11 \cdot 13 = 1001,$ the Chinese remainder theorem gives exactly $2 \cdot 6 \cdot 8 = 96$ safe residues modulo $1001,$ so each block of $1001$ consecutive integers contains $96$ safe numbers.

The integers $1$ through $10010$ form ten such blocks, containing $960$ safe numbers. It remains to discard the safe numbers among $10001, \ldots, 10010.$ Their residues modulo $7$ run $5, 6, 0, 1, 2, 3, 4, 5, 6, 0,$ so only $10006$ and $10007$ are $7$ -safe; both are also $11$ -safe (residues $7$ and $8$ ) and $13$ -safe (residues $9$ and $10$ ).

Therefore the count is $960 - 2 = 958.$

2012 AIME II 第 12 题

答案：958

难度评级：2920

解答：

其他年份的第 12 题