POJ 2407Relatives

2018-01-27 11:14:41来源:cnblogs.com作者:自为风月马前卒人点击

分享
Relatives
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 15566 Accepted: 7900

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

7120

Sample Output

64

Source

Waterloo local 2002.07.01  题目大意给定$n$,求出$/varphi /left( n/right)$直接套公式。$/varphi /left( n/right) =n/prod ^{k}_{i=1}/left( /dfrac {p_{i}-1}{p_{i}}/right)$注意先除再乘,否则会爆精度 
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#define LL long long using namespace std;int main(){    LL N;    while(cin>>N&&N!=0)    {        int limit=sqrt(N),ans=N;        for(int i = 2; i <= limit ; ++i)        {            if(N%i==0) ans=ans/i*(i-1);            while(N%i==0) N=N/i;        }        if(N>1) ans=ans/N*(N-1);        printf("%d/n",ans);    }    return 0;}
   

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台