NYOJ----333mdd的煩惱

mdd的煩惱

1000 ms  |  記憶體限制：

65535

3

今天mdd看到這麼一段話：在數論，對正整數n，歐拉函數是少于或等于n的數中與n互質的數的數目。此函數以其首名研究者歐拉命名，它又稱為Euler's totient function、φ函數、歐拉商數等。 例如φ(8)=4，因為1,3,5,7均和8互質。于是他想用計算機實作歐拉函數的功能，但是他又不想去寫，你能幫幫他嗎？

互質（relatively primeì）又叫互素。若N個整數的最大公因數是1，則稱這N個整數互質。

有多組測試資料組數小于1003，

每組測試資料有一個整數n(0<n<=65535^2+1).

輸出

輸出歐拉函數φ(n)的值。

樣例輸入

2

6

46

樣例輸出

1

2

22

思路：考查歐拉函數，定義：在數論，對正整數n，歐拉函數是少于或等于n的數中與n互質的數的數目。此函數以其首名研究者歐拉命名，

一開始直接看懂題意就去敲代碼了，wrong了之後才發現沒有注意題中的給的資料範圍。

還是因為平時沒有養成好的程式設計習慣，望大家也要注意，引以為鑒啊。

吸取教訓之後，認真的就先出了，還是那就話：世上無難事隻怕有心人！

錯誤，正确的代碼一并附上吧。

/***************
Result:wrong answer
**************/
#include<stdio.h>
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int n,sum;
    while(~scanf("%d",&n))
    {
        int i,j,sum=0;
        for(i=1; i<n; i++)
        {
            if(gcd(i,n)==1)
                sum++;
        }
        printf("%d\n",sum);
    }

}
 

/*************
Author:jiabeimuwei
Times:68ms;
Sources:NYOJ333
**************/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
using namespace std;
//#include<windows.h>
//#include<conio.h>
#define max(a,b) a>b?a:b
#define min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
#define malloc(sb) (sb *)malloc(sizeof(sb))
//int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};
long long oula(long long x)
{
    long long t=x;
    for(long long i=2; i*i<=x; i++)
        if(x%i==0)
        {
            while(!(x%i))x/=i;
            t=t/i*(i-1);
        }
    if(x!=1)
        t=t/x*(x-1);
    return t;
}
int main()
{
    long long n;
    while(scanf("%lld",&n)!=EOF)
        printf("%lld\n",oula(n));
    return 0;
}

 最優代碼（參考了學長的）：
  
#include<iostream>
#include<cstdio>
using namespace std;
long long Eular(long long n)
{
    int i;
    long long ret=n;
    for(i=2;i*i<=n;++i)
    {
        if(n%i==0)
        {
            ret-=ret/i;
            while(n%i==0)n/=i;//去掉n中含有的所有i因子
            if(n==1)break;
        }
    }
    if(n!=1)ret-=ret/n;
    return ret;
}
int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    long long m;
    while(~scanf("%lld",&m))
        printf("%lld\n",Eular(m));
}