欧拉反演
geven
·
·
个人记录
欧拉反演
定理：
n = \sum\limits_{d \mid n} \varphi(d)
证明
显然对于一个 i ~ (1 \leq i \leq n)，i 与 n 的 \gcd 都是唯一的。
由此可得：
n = \sum\limits_{d \mid n} \sum\limits_{i=1}^{n} ~ [\gcd(i,n) = d]
此公式相当于枚举 \gcd。由于 i 与 n 的 \gcd 唯一，所以统计时只会贡献一次。
将公式变形，得：
n = \sum\limits_{d \mid n} \sum\limits_{i=1}^{n} ~ [d \mid i,~\gcd(\frac{i}{d},\frac{n}{d})=1]
发现内层循环就是求在 \frac{n}{d} 范围内与 \frac{n}{d} 互质的数的个数，即为 \varphi(\frac{n}{d})。
再次将公式变形，得：
n = \sum\limits_{d \mid n} \varphi(\frac{n}{d})
由于 d \mid n，所以 d 与 \frac{n}{d} 的值一一对应。
所以进行最后的变形，得：
n = \sum\limits_{d \mid n} \varphi(d)
证毕。
应用
给定一个 n \thinspace(1 \leq n \leq 10^{12})，求 \sum\limits_{i=1}^{n} \gcd(i,n)。
推导
设答案为 ans。
对 \gcd(i,n) 进行欧拉反演，得：
ans = \sum\limits_{i=1}^{n} \sum\limits_{d \mid \gcd(i,n)} \varphi(d)
观察到：若 d \mid \gcd(i,n)，则符合条件的 d 要满足的充要条件是 d \mid i,d \mid n。
根据上述性质，改写得：
ans = \sum\limits_{i=1}^{n} \sum\limits_{d \mid i,d \mid n} \varphi(d)
将内层循环移至外层，得：
ans = \sum\limits_{d \mid n} \sum\limits_{i=1}^{n} \varphi(d) \thinspace [d \mid i]
将 \varphi(d) 移至外层循环，得:
ans = \sum\limits_{d \mid n} \varphi(d) \sum\limits_{i=1}^{n} \thinspace [d \mid i]
发现在 n 以内，d \mid i 的个数就是 \lfloor \frac{n}{d} \rfloor。
最终改写得：
ans = \sum\limits_{d \mid n} \lfloor \frac{n}{d} \rfloor \thinspace \varphi(d)
时间复杂度
对 n \thinspace (1 \leq n \leq 10^{12}) 进行质因数分解：
n = p_1^{r_1} p_2^{r_2} \cdots p_k^{r_k}
当 n 的因数个数最多时，r_1 = r_2 = \cdots = r_k = 1。
在 10^{12} 范围内，满足条件的最大数是：
200560490130 = 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 \times 31
此时因数个数为 2^{11}=2048，不算很多，时间复杂度足以通过本题。