给出一个n，求1-n这n个数，同n的最大公约数的和。比如：n = 6
1,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6，加在一起 = 15
Input
1个数N(N <= 10^9)1个数N(N <= 10^9) Output
公约数之和公约数之和 Input示例
66 Output示例
115 $ans=\sum_{i=1}^ngcd\left(i,n\right)$
$=\sum_{i=1}^n\sum_{j\mid i,j\mid n}\varphi\left(j\right)$
$=\sum_{i\mid n}\frac{n\varphi\left(i\right)}{i}$
然后$O(\sqrt{n})$的时间枚举因子，暴力求欧拉函数值即可
#includeint phi(int n){int ans = n;for(int i = 2; i * i <= n; i++){if(n % i == 0){ans -= ans / i;while(n % i == 0) n /= i;}}if(n != 1) ans -= ans / n;return ans; } int main(){int n;long long ans = 0;scanf("%d", &n);for(int i = 1; i * i <= n; i++){if(n % i == 0){ans += (long long) n * phi(i) / i;if(i * i != n) ans += (long long) n * phi(n / i) * i / n;} }printf("%lld\n", ans);return 0; }
