问题 W: Longge's problem
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:6
解决:3
题目描述
Longge is good at mathematics and he likes to think about hard mathematical problems which will be solved by some graceful algorithms. Now a problem comes: Given an integer N(1<N<231),you are to calculate ∑gcd(i,N) 1≤i≤N.
"Oh, I know, I know!" Longge shouts! But do you know? Please solve it.
"Oh, I know, I know!" Longge shouts! But do you know? Please solve it.
输入
Input contain several test case.
A number N per line.
A number N per line.
输出
For each N, output ,∑gcd(i,N) 1≤i≤N, a line
样例输入 复制
2
6
样例输出 复制
3
15