题目来源： 

基准时间限制：1 秒 空间限制：131072 KB 分值: 80 

 收藏

 关注

给出一个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)

Output

公约数之和

Input示例

6

Output示例

15

思路：

目的是求∑（i= 1，n） gcd( i , n )；

gcd( i , n ) = x，表示x是n的因子。稍作变形gcd( i / x , n / x) = 1，

看到这个式子可以想到欧拉函数，也就是求比n/x小的与其互质的个数。

因为这些书和n/x互质，乘上x后与n的最大公约数只有x。

也就是说我们先求出每个因子，然后计算每个因子有多少贡献即可。

 

 

/* * Author:  sweat123 * Created Time:  2016/6/27 14:01:46 * File Name: main.cpp */#include
      
       #include