QOJ.ac

QOJ

Time Limit: 0.5 s Memory Limit: 128 MB Total points: 100

# 4136. Longge 的问题

Statistics

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}$。