「POJ2407」Relatives

2014年6月1日3,2780

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

题解

计算公式为：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有不重复的质因数

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int n;
int cal(int x)
{
    int t=x;
    for(int i=2;i<=(int)sqrt(x);i++)
        if(x%i==0)
        {
            t=t/i*(i-1);
            while(x%i==0)x/=i;
        }
    if(x>1)t=t/x*(x-1);
    return t;
}
int main()
{
    while(scanf("%d",&n))
    {
        if(n==0)break;
        printf("%d\n",cal(n));
    }
    return 0;
}

#include<cstdio>

#include<cmath>

#include<iostream>

using namespace std;

int n;

int cal(int x)

{

int t=x;

for(int i=2;i<=(int)sqrt(x);i++)

if(x%i==0)

{

t=t/i*(i-1);

while(x%i==0)x/=i;

}

if(x>1)t=t/x*(x-1);

return t;

}

int main()

{

while(scanf("%d",&n))

{

if(n==0)break;

printf("%d\n",cal(n));

}

return 0;

}

« NOI2002Robot 「BZOJ2818」Gcd »

hzwer.com _ Home | http://hzwer.com

「POJ2407」Relatives

分类目录

热门文章

Myfriends

近期评论