NOIP 普及组初赛 · NOIP 2018 普及组初赛试题 第 13 题

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

这道题考欧拉函数，核心就一句：先把10000拆成质因数，只盯住不同的质数2和5，套公式φ(n)=n×(1−1/2)×(1−1/5)算出4000，注意别把指数4当成4个不同质因子去乘，那是最大坑。

最容易栽跟头的就是数错不同质因子的个数。10000=2⁴×5⁴，虽然指数是4，但不同的质因子只有2和5两个，公式里每个不同的质因子只乘一次(1−1/p)。很多学生会误以为有4个不同质因子，结果把φ(10000)算成10000×(1/2)×(4/5)×(9/10)×(16/17)之类的荒谬数字，或者干脆把指数4当成4个质因子去乘，导致答案变成2000或8000。记住，欧拉函数看的是质因子的种类，不是次数。

考点与概念

这题考查欧拉函数φ(n)：1到n之间有多少个数和n互质（即最大公约数为1）。互质的直观理解就是两个数没有共同的除数（除了1）。比如3和10互质，4和10不互质。

命题视角

命题人喜欢挖的坑就两个： 1. 混淆指数与种类：看到10000=2⁴×5⁴，容易误以为有4个不同质因子，从而多乘几项。 2. 公式套错：以为每个质因子的幂次都要参与乘法，其实φ(n)的公式里，每个不同的质因子只乘一次(1−1/p)，跟指数a,b,c完全无关。