1286: 小明的数学问题

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：33 Solved：13

Description

小明的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i，n)(1<=i <=n)。说明：gcd（i，n）表示i和n的最大公约数，∑gcd(i，n)(1<=i<=n)表示求1~n之间的每一个数与n的最大公约数之和。

Input

一个整数N

Output

一个整数，为所求的答案。

Sample Input Copy 

6

Sample Output Copy 

15

HINT

【数据说明】

对于60%的数据，1<=N<=2^16

对于100%的数据，1<=N<=2^32

Source/Category

SubmitSubmit RecordStatisticsShowOff!