[SDOI2012]Longge的问题

Longge 的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数 $N$，你需要求出

$\sum_{i=1}^{N}\gcd(i, N).$

输入格式

一个整数，为 $N$。

输出格式

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

样例输入

6

样例输出

15

样例解释

$N=6$ 时，

$\gcd(1,6)+\gcd(2,6)+\gcd(3,6)+\gcd(4,6)+\gcd(5,6)+\gcd(6,6)=1+2+3+2+1+6=15.$

数据范围

• $0<N\le 2^{32}$。

来源与许可

本题为 SDOI 2012 试题「Longge的问题」，题面与测试数据整理自 BZOJ 2705。

样例 1

输入

6

输出

15