eolymp
bolt
Try our new interface for solving problems
Məsələlər

Проблема Лонги

Проблема Лонги

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Лонги хорошо разбирается в математике, он любит задумываться над трудными математическими задачами, которые могут быть решены при помощи некоторых изящных алгоритмов. И вот такая задачка возникла:

Дано целое число n. Вычислите ∑gcd(i, n) для всех 1 \le i \le n.

"О, я знаю, я знаю!" - воскликнул Лонги! А знаете ли Вы? Пожалуйста, решите её.

Giriş verilənləri

Каждая строка содержит одно число n~(1 < n < 2^{31}).

Çıxış verilənləri

Для каждого значения n выведите в отдельной строке сумму ∑gcd(i, n) для всех 1 \le i \le n.

Nümunə

Giriş verilənləri #1
2
6
12
Çıxış verilənləri #1
3
15
40