「Longge's problem」 龙哥的问题

龙哥现在有一道题，要考考大家。

给定一个整数N，请你求出$\sum\_{1 \le i \le N} gcd（i，N)$的值。

输入格式

一个整数N。

输出格式

一个整数表示结果。

数据范围

$1 < N < 2^{31}$

输入样例：

6

输出样例：

15

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解