【題目大意】:歐拉函數:求少於或等於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; }
版權聲明:本文為博主原創文章,未經博主允許不得轉載。