NOIP 普及 2018 第一轮 第 13 题：10000 以内与 10000 互质的正整数个数

题目

$10000$ 以内，与 $10000$ 互质的正整数有（ ）个。

选项

• A. 2000
• B. 4000
• C. 6000
• D. 8000

答案

B

题解

考点定位

本题考「欧拉函数」,对应大纲 2.1.3 数论（难度【3】）。

解题过程

10000 = 2⁴×5⁴。φ(10000) = 10000×(1/2)×(4/5) = 4000。

选 B。

易错提醒

① 与 10000 互质 = φ(10000)（含 1，且 10000 本身不互质自动排除）；② φ(p^k)=p^k−p^(k−1)。