Comet OJ

C0926 [SDOI2012]Longge的问题

内存限制：256 MB 时间限制：1000 ms

题目描述

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

输入格式

一个整数，为 $N$。

输出

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

样例

样例输入 1

6

样例输出 1

15

提示

对于 $60\%$ 的数据，$0<N \le 2^{16}$。

对于 $100\%$ 的数据，$0<N \le 2^{32}$。