PA2013 Euler
给一个正整数 \(n\)，找到所有的 \(a\) 使得 \(\varphi(a)=n\)，其中 \(\varphi\) 是 Euler totient function .
\(n\le 10^{10}\) .
令 \(\displaystyle n=\prod_{i=1}^kp_i^{\alpha_i}\)，其中 \(p_i\) 是素数，\(\alpha_i>0\)，则
\[\varphi(n)=\prod_{i=1}^kp_i^{\alpha_i-1}(p_i-1) \]这是一个和广为流传的写法不一样的，阳间一点的欧拉函数式子 .
考虑枚举 \(n\) 的每个约数 \(d\)，若 \(d+1\) 是素数那么就有可能作为答案的质因子出现 .
于是暴力 DFS，对于每个数 \(n\)，每次枚举下一个要在答案中出现的素因子 \(p\)，然后令 \(n\gets \dfrac n{p-1}\) 即可 .
不难发现只有 \((p-1)\mid n\) 才可能有解，于是令 \(D_{i,j}\) 表示第 \(i\) 个约数在第 \(j\) 个素数之后第一个能被整除的位置，转移的时候按 \(D\) 枚举即可，\(D\) 的预处理是平凡的 .
还得判一下一个因子 \(d\) 在 \(n\) 的所有因子中的排名，按 \(\sqrt n\) 分治即可用两个长 \(\sqrt n\) 的数组维护 .
注意 \(n=1\) 时跳出 .
时间复杂度 \(O(\sqrt n\log n)\)，可能分析的不准，轻 D .
洛谷提交记录 R84926290 .
标签：社论,PA2013,varphi,枚举,sqrt,alpha,Euler From： https://www.cnblogs.com/CDOI-24374/p/16618297.html