北京海淀区信息学竞赛 · 2023 北京市海淀区信息学竞赛（初赛）试题 第 17 题

在不超过 $10000$ 的正整数中，与 $10000$ 互质的正整数有（ ）个。

这题考欧拉函数φ(n)，核心就是数1到n里和n互质的个数。别慌，10000分解质因数很简单，套公式就能算出结果。

学生最容易把'互质'理解成'相邻'，误以为只有1和n互质，或者死记硬背φ(n)=n-1这种错误结论。还有人选A或D，那是没考虑n的质因数个数，把公式记混成'质因数个数'或'质因数个数加1'了。

这道题考查欧拉函数φ(n)，也就是小于等于n且与n互质的正整数个数。别被'互质'吓到，其实就是最大公约数为1。命题人爱考大数，但10000这种数分解质因数特别顺手，就是挖坑让你别用暴力枚举。拿到题先想：10000能不能拆成几个质数幂的乘积？一眼看出10000=10^4=(2×5)^4=2^4×5^4。欧拉函数的公式是φ(n)=n×(1-1/p1)×(1-1/p2)×…，对每个质因数pi都乘一个(1-1/pi)。这里两个质因数2和5，所以φ(10000)=10000×(1-1/2)×(1-1/5)=10000×1/2×4/5=4000。计算过程要细心：先约分再乘，或者按顺序乘，别把分数算错。避坑指南：别以为φ(n)=n-1，那是n是质数才成立；也别把公式记成'质因数个数'，那是另一回事。考频趋势看2023海淀区信息学竞赛，欧拉函数这类数论基础题出现频率中等，是必考点。预测未来可能继续考大数分解质因数后套公式，或者结合同余、模运算出更复杂的数论题，但公式本质不变。