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 .
Original: https://www.cnblogs.com/CDOI-24374/p/16618297.html
Author: Jijidawang
Title: PA2013 Euler 社论
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584435/
转载文章受原作者版权保护。转载请注明原作者出处！