题目描述

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

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

输入格式

一个整数N。

输出格式

一个整数表示结果。

数据范围

$1 < N < 2^{31}$

输入样例：

6

输出样例：

15

来源

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