2001 AIME II 第 10 题

先试着解答 2001 AIME II 第 10 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2001 AIME II 解答,或核对答案

所有题目均经美国数学协会(MAA)官方合法授权使用。

10.

有多少个 10011001 的正整数倍可以表示为 10j10i10^{j} - 10^{i} 的形式,其中 iijj 是整数且 0i<j990 \le i \lt j \le 99

How many positive integer multiples of 10011001 can be expressed in the form 10j10i,10^{j} - 10^{i}, where ii and jj are integers and 0i<j99?0 \le i \lt j \le 99?

答案:784
知识点:乘法阶模运算数对计数
难度评级:2710
解答:

分解得 10j10i=10i(10ji1)10^j - 10^i = 10^i(10^{j-i} - 1)。由于 1001=711131001 = 7 \cdot 11 \cdot 1310i10^i 互质,我们需要 100110ji11001 \mid 10^{j-i} - 1101077、模 1111、模 1313 的乘法阶分别为 662266,所以 10k1(mod1001)10^k \equiv 1 \pmod{1001} 当且仅当 kk66 的倍数。不同的 (i,j)(i, j) 给出不同的值,因此只需计数这些有序对。

ji=6dj - i = 6d,其中 1d161 \le d \le 16,则 ii 可取 0,1,,996d0, 1, \ldots, 99 - 6d,共有 1006d100 - 6d 种。总数为 d=116(1006d)=94+88++4=(94+4)162=784. \begin{aligned} &\sum_{d=1}^{16} (100 - 6d) \\ &= 94 + 88 + \cdots + 4 \\ &= \frac{(94 + 4) \cdot 16}{2} \\ &= 784. \end{aligned}

Factor 10j10i=10i(10ji1).10^j - 10^i = 10^i(10^{j-i} - 1). Since 1001=711131001 = 7 \cdot 11 \cdot 13 is coprime to 10i,10^i, we need 100110ji1.1001 \mid 10^{j-i} - 1. The multiplicative order of 1010 is 66 modulo 7,7, 22 modulo 11,11, and 66 modulo 13,13, so 10k1(mod1001)10^k \equiv 1 \pmod{1001} exactly when kk is a multiple of 6.6. Distinct pairs (i,j)(i, j) give distinct values, so we just count the pairs.

For ji=6dj - i = 6d with 1d16,1 \le d \le 16, the index ii can be 0,1,,996d,0, 1, \ldots, 99 - 6d, giving 1006d100 - 6d choices. The total is d=116(1006d)=94+88++4=(94+4)162=784. \begin{aligned} &\sum_{d=1}^{16} (100 - 6d) \\ &= 94 + 88 + \cdots + 4 \\ &= \frac{(94 + 4) \cdot 16}{2} \\ &= 784. \end{aligned}

← 第 9 题#9
完整试卷

其他年份的第 10 题