## Longge's problem

### 题目描述

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 < 2^{31}$),you are to calculate $\sum gcd$($i, N$) $1 \le i \le N$.

"Oh, I know, I know!" Longge shouts! But do you know? Please solve it.

### 输入格式

Input contain several test case.
A number $N$ per line.

### 输出格式

For each $N$, output ,$\sum gcd$($i,N$) $1 \le i \le N$, a line

### 样例输入

2
6


### 样例输出

3
15


## 题解

$\phi$($p^k$)$=p^k-p^{k-1}=p^{k-1}*(p-1)$

$\phi$($p*k$)$=\phi$($p$)$*\phi$($k$)

inline long long phi(long long x){
long long sum=x;
for(long long j=2;j*j<=x;j++)
if(x%j==0){
while(x%j==0) x/=j;
sum=sum/j*(j-1);
}
if(x!=1) sum=sum/x*(x-1);
return sum;
}

ps：有多组数据

#include<cstdio>
using namespace std;
long long n;
inline long long fd(long long x){
long long sum=x;
for(long long j=2;j*j<=x;j++){
if(x%j==0){
while(x%j==0) x/=j;
sum=sum/j*(j-1);
}
}
if(x!=1) sum=sum/x*(x-1);
return sum;
}
long long sum;
int main(){
while(scanf("%lld",&n)!=EOF){
sum=0;
for(long long i=1;i*i<=n;i++){
if(n%i==0) sum+=fd(n/i)*i;
long long u=n/i;
if(u!=i && n%u==0) sum+=fd(n/u)*u;
}
printf("%lld\n",sum);
}
return 0;
}