NYOJ570---歐拉函數求和

570 歐拉函數求和      

時間限制：1000 ms  |  記憶體限制：65535 KB

難度：3

 題目描述很簡單，求出：

 （PS:上面式子的意思是大于0小于n并且能整除n的所有d的歐拉函數值之和）。

 輸入

    每行一個數n（n<2^31)，輸入以檔案結尾結束。

輸出

    每個結果占一行。

樣例輸入

  1

    2

    12

 樣例輸出

  1

  8

/**************
Author:jiabeimuwei
Times:0ms
Sources:NYOJ570
**************/ 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
LL Euler(LL n)
{
    LL sum=n;
    for(LL i=2; i*i<=n; i++)
    {
        if(n%i==0)
        {
            while(n%i==0) n=n/i;
            sum=sum/i*(i-1);
        }
    }
    if(n>1) sum=sum/n*(n-1);
    return sum;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        LL sum=0;
        for(int i=1; i*i<=n; i++)
        {
            if(n%i==0)
            {
                if(i!=n)
                    sum+=Euler(i);
                if(i*i!=n&&i!=1) 
                   sum+=Euler(n/i);
            }
        }
        printf("%lld\n",sum);
    }
    return 0;
}
學長的比較好的代碼：
#include<stdio.h>
int Eular(int  n)
{
    int i;
    int  ans=n;
    for(i=2; i*i<=n; ++i)
    {
        if(n%i==0)
        {
            ans-=ans/i;
            while(n%i==0)
                n=n/i;
            if(n==1)
                break;
        }
    }
    if(n!=1)
        ans-=ans/n;
    return ans;
}
int main()
{
    int i, j, k, n, x;
    while( ~scanf("%d",&n) )
    {
        int sum = 0;
        if(n==1)
        {
            puts("0");
            continue;
        }
        for(i=1; i*i<=n; i++)
        {
            if(n%i==0)
            {
                sum+=(Eular(i));
                if( i!=1 && i*i!=n )
                    sum+=(Eular(n/i));
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}