Time Limit: 1s → 0.5s
Longge 的数学成绩非常好,并且他非常乐于挑战高难度的数学问题。现在问题来了:给定一个整数 $N$,你需要求出 $\sum_{i=1}^N \gcd(i, N)$。
输入格式
一个整数,为 $N$。
输出格式
一个整数,为所求的答案。
样例数据
样例输入
6
样例输出
15
子任务
对于 $60\%$ 的数据,$0 < N \leq 2^{16}$。
对于 $100\%$ 的数据,$0 < N \leq 2^{32}$。