#748. 最大公约数

最大公约数

无额外样例。

题目描述

给出一个整数 nn,求

∑i=1ngcd⁡(i,n)\sum \limits_{i=1}^n \gcd(i, n)

其中 gcd⁡(i,n)\gcd(i, n) 表示 ii 和 nn 的最大公约数。

输入格式

一个整数,表示 nn。

输出格式

一个整数,表示答案。

样例1输入

4

样例1输出

8

样例2输入

4000000004

样例2输出

212438171400

数据范围

  • 60%60\% 的数据:n≤216n ≤ 2^{16}。
  • 100%100\% 的数据:1≤n<2321 ≤ n < 2^{32}。