poj2480-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 ∑gcd(i, N) 1<=i <=N.

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

Input

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

Output

For each N, output ,∑gcd(i, N) 1<=i <=N, a line

Sample Input

2
6

Sample Output

3
15
翻译：给一个数n,1<=i<=n,求gcd(i,n)之和。
解题过程：
令d=gcd(i,n)，d必然是n的因子，并且是i和n的最大公因子。
则gcd(i/d,n/d)=1。令y=n/d,通过y求出与y互质的数的个数，然后对这个数量乘以最大公因子d，累加。

 1 #include <iostream>
 2 #include<stdio.h>
 3 #include <algorithm>
 4 #include<string.h>
 5 #include<cstring>
 6 #include<math.h>
 7 #define inf 0x3f3f3f3f
 8 #define ll long long
 9 using namespace std;
10 
11 ll euler(ll x)
12 {
13     ll res=x;
14     for(ll i=2;i*i<=x;i++)
15     {
16         if(x%i==0)
17         {
18             res=res/i*(i-1);
19             while(x%i==0)
20                x=x/i;
21         }
22     }
23     if(x>1)
24         res=res/x*(x-1);
25     return res;
26 }
27 
28 int main()
29 {
30     ll n,sum;
31     while(scanf("%lld",&n)!=EOF)
32     {
33         sum=0;
34         ll i;
35         for(i=1;i*i<=n;i++)
36         {
37             if(n%i==0)
38                 sum+=i*euler(n/i)+(n/i)*euler(i);
39         }
40         i--;
41         if(i*i==n)
42             sum-=i*euler(i);
43         printf("%lld
",sum);
44     }
45     return 0;
46 }