POJ 2407 Relatives && UVA 10299 Relatives（歐拉函數）

【題目大意】：歐拉函數：求少於或等於n的數中與n互素的數的個數；n <= 1,000,000,000。

【思路】：裸歐拉函數，注意特判n==1的情況，n==1的情況下，應該輸出0，poj依然判斷1也可以過，但是老牌ojUVA必須是0才過，注意一下。

代碼：

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;

int eular(int n){
    int res=n;
    for(int i=2; i*i<=n; ++i){
        if(n%i==0){
            n/=i;res=res-res/i;
            while(n%i==0)
            {
                n/=i;
            }
        }
    }
    if(n!=1) res=res-res/n;
    return res;
}
int main()
{
    int n;while(cin>>n&&n!=0)
    {
        if(n==1) puts("0");
        else printf("%d\n",eular(n));
    } return 0;
}

版權聲明：本文為博主原創文章，未經博主允許不得轉載。