POJ 2407 Relatives（欧拉函数入门题）

Relatives

Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.

Input

There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.

Output

For each test case there should be single line of output answering the question posed above.

Sample Input

Sample Output

6

4

题意：输入个n，求（1，n-1）与n互质的个数有多少个
思路：这明显就是欧拉函数模版题，就是求n的欧拉数

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long ll;

ll phi(ll n)//求n的欧拉数

{

    ll sum=n;

    for(int i=;i*i<=n;i++)//O（根号n的复杂度）

    {

        if(n%i==)

        {

            sum=sum-sum/i;

            do

            {

                n/=i;

            }while(n%i==);

        }

    }

    if(n>) sum=sum-sum/n;

    return sum;

}

int main()

{

    ll n;

    while(scanf("%lld",&n)!=EOF)

    {

        if(n==)

        break;

        printf("%lld\n",phi(n));

    }

}

巴特西

POJ 2407 Relatives（欧拉函数入门题）

Relatives

最新文章

热门文章