题目描述

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

给定一个整数 $N$，请你求出 $∑_{1≤i≤N}{gcd(i，N)}$的值。

输入格式

一个整数$N$。

输出格式

一个整数表示结果。

样例

6

15

数据范围

$1<N<2^{31}$

来源

• SDOI2012
• POJ2480
• 算法竞赛进阶指南