程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2407 Relatives && UVA 10299 Relatives(歐拉函數)

POJ 2407 Relatives && UVA 10299 Relatives(歐拉函數)

編輯:C++入門知識

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;
}


 

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved