Longge`s problem#1128
Longge is good at mathematics, and he likes to think about difficult mathematical problems that can be solved using elegant algorithms. Now he faces the following problem:
Given an integer , compute \sum \gcd(i,n) for all 1 \leq i \leq n.
"Oh, I know, I know!" Longge shouts. But do you? Please solve it.
Each line contains one integer n~(1 < n < 2^{31}).
For each integer , print on a separate line the sum \sum \gcd(i,n) for all 1 \le i \le n.
Example 1