首页 > 代码库 > [POJ 2407]Relatives(欧拉函数)

[POJ 2407]Relatives(欧拉函数)

2024-07-18 15:42:46   227人阅读

Description

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

7
12
0

Sample Output

6
4

Source

Waterloo local 2002.07.01

刚开始我傻X了，本着蒟蒻的思维，照着欧拉函数的公式写了如下的代码，先筛素数然后分解质因数最后再算公式

//欧拉函数h(n)=n*(1-1/p1)*(1-1/p2)*'''''*(1-1/pk);
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

#define MAXN 1010

using namespace std;

bool isPrime[MAXN];
int Prime[MAXN],PriNum[MAXN],cnt=0,tot=0;

void GetPrime()
{
    cnt=0;
    for(int i=1;i<MAXN;i++) isPrime[i]=true;
    for(int i=2;i<MAXN;i++)
    {
        if(isPrime[i])
        {
            Prime[++cnt]=i;
            for(int j=2*i;j<MAXN;j+=i)
                isPrime[j]=false;
        }
    }
}

void DecQualityFactor(int n) //分解质因数
{
    tot=0;
    for(int i=1;Prime[i]*Prime[i]<=n;i++)
    {
        if(n%Prime[i]==0)
        {
            PriNum[++tot]=Prime[i];
            while(!(n%Prime[i])) n/=Prime[i];
        }
    }
    if(n!=1) PriNum[++tot]=n;
}

int h(int n)
{
    double ans=n;
    for(int i=1;i<=tot;i++)
    {
        ans*=(1.0-1.0/(double)PriNum[i]);
    }
    return (int)ans;
}

int main()
{
    GetPrime();
    while(1)
    {
        cnt=0,tot=0;
        memset(PriNum,0,sizeof(PriNum));
        int N;
        cin>>N;
        if(!N) break;
        DecQualityFactor(N);
        cout<<h(N)<<endl;
    }
    return 0;
}
好吧这个代码根本没办法过，因为题目给的n的范围太大了，数组完爆内存，也就是说这题根本就不能用数组保存什么质因数和素数的。
下面才是真正的AC代码，又短又快神神哒

//欧拉函数h(n)=n*(1-1/p1)*(1-1/p2)*'''''*(1-1/pk);
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

#define MAXN 1000

using namespace std;

int h(int n)
{
    int ans=n;
    for(int i=2;i<=n;i++)
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            n/=i;
            while(n%i==0) n/=i;
        }
    }
    return ans;
}
int main()
{
    while(1)
    {
        int N;
        cin>>N;
        if(!N) break;
        cout<<h(N)<<endl;
    }
    return 0;
}





联系
我们