2024 年江苏预赛

思路

若 $n=\prod p^{a_p}$，则 $\phi (n)=\prod p^{a_p-1}(p-1)$，由排除各质因数倍数的容斥可得。欧拉函数只在正整数上讨论。

想法从哪来：反求欧拉函数若直接枚举整数，无法保证穷尽；先看目标函数值里没有因子5，却已知原数含5，这迫使原数只含一个5。剥离之后，目标成为一个质因数很少的小乘积。欧拉公式说明原数每有质数p，就必须向函数值贡献p-1，因此候选p可从目标的因数加一逐个筛选。还要留意质数幂会额外贡献p的幂：这使某个目标质因数既可能来自更高次幂，也可能来自另一质数减一。比较两种来源的总因子开销，可以排除看似可能的组合。最后别漏掉乘一个互素的2不改变奇数欧拉值这一特殊分支。

先剥离质因数 $5$，再利用“若质数 $p$ 整除整数，则 $p-1$ 整除其欧拉函数值”限定所有可能质因数。