描述
求Σgcd(i, n), 0<N≤2^32
分析
- 直接求是不行的, 可以分析满足gcd(i, n) = j 的 i 有多少个, 再用 j 乘上这个个数.
- 如果gcd(i, n) = j, 那么gcd(i/j, n/j) = 1, 又由于i≤n, 所以gcd(i/j, n/j) = 1的个数就是不超过n/j并与n/j互质的数的个数, 即φ(n/j).
- 所以Σgcd(i, n) = j * φ(n/j),
j | n.
- 枚举n的因子j, 统计
j*φ(n/j) + n/j*j * φ(j). O(sqrt(n) * sqrt(sqrt(n)))
- 还有种更简单的方法, 但是没看懂
代码
BZOJ-2705-Longge的游戏-SDOI2012-欧拉函数
原文：http://blog.csdn.net/qq_21110267/article/details/44569107
