2014 AIME I 第 3 题

Question

求有多少个有理数

r

，满足

0 \lt r \lt 1

，并且当

r

写成最简分数时，分子和分母之和为

1000

。

Find the number of rational numbers

r,

0 \lt r \lt 1,

such that when

r

is written as a fraction in lowest terms, the numerator and the denominator have a sum of

1000.

答案

答案：200

知识点：欧拉函数最大公约数分数

难度评级：2110

小提示：

将

r = \frac{a}{b}

写成最简分数；则

a + b = 1000

，且

a \lt 500

Write

r = \frac{a}{b}

in lowest terms; then

a + b = 1000

with

a \lt 500

大提示：

\gcd(a, 1000 - a) = \gcd(a, 1000)

，所以只需数出满足

a \lt 500

且与

1000

互质的数

\gcd(a, 1000 - a) = \gcd(a, 1000),

so count

a \lt 500

that are coprime to

1000

解答：

将

r = \frac{a}{b}

写成最简分数，且

a + b = 1000

；由于

0 \lt r \lt 1

，需要

1 \le a \le 499

。又因为

\gcd(a, b) = \gcd(a, 1000 - a)

= \gcd(a, 1000)

，这个分数为最简分数当且仅当

a

与

1000

互质。

欧拉函数给出

\varphi(1000) = 1000 \cdot \frac{1}{2} \cdot \frac{4}{5} = 400

，即在

[1, 999]

中，与

1000

互质的整数共有这么多个。它们按

a \leftrightarrow 1000 - a

成对出现（注意

a = 500

与

1000

不互质），所以其中恰有

200

个小于

500

。答案为

200

。

Write

r = \frac{a}{b}

in lowest terms with

a + b = 1000;

since

0 \lt r \lt 1,

we need

1 \le a \le 499.

Because

\gcd(a, b) = \gcd(a, 1000 - a)

= \gcd(a, 1000),

the fraction is in lowest terms exactly when

a

is coprime to

1000.

There are

\varphi(1000) = 1000 \cdot \frac{1}{2} \cdot \frac{4}{5} = 400

integers in

[1, 999]

coprime to

1000,

and they pair up as

a \leftrightarrow 1000 - a

(note

a = 500

is not coprime to

1000

), so exactly

200

of them are less than

500.

The answer is

200.

2014 AIME I 第 3 题

答案：200

难度评级：2110

小提示：

大提示：

解答：

其他年份的第 3 题