Description

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。

Input

一个整数，为N。

Output

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

Sample Input

6

Sample Output

15

HINT

【数据范围】

对于60%的数据，0<N<=2^16。

对于100%的数据，0<N<=2^32。

题解

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

用惯用的套路我们枚举 $N$ 的因子  $$\sum_{d \mid N} d \cdot \sum_{i = 1}^{ \frac{N}{d} } \left[gcd \left( \frac{N}{d} , i \right) = 1\right]$$

化简为 $$\sum_{d \mid N} d \cdot \varphi \left( \frac{N}{d} \right)$$

欧拉函数直接用 $\varphi(n) = n \cdot \prod_{i = 1}^k \left(1-\frac{1}{p_i} \right)$ 来求。

1 //It is made by Awson on 2018.1.12 2 #include 
     
       3 #include