U - Relatives（欧拉函数）

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

解题思路：欧拉函数：求不大于n且与n互质的数的个数。

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 int Euler(int x){

     int r=x;

     for(int i=;i*i<=x;i++){//由于任何一个合数都至少有一个不大于根号x的质因子，所以只需遍历到根号x即可

         if(x%i==){

             r=r/i*(i-);//欧拉函数的通式，先除后乘，避免数据溢出

             while(x%i==)x/=i;//消除x中所有质因子i，直到不能被i整除

         }

     }

     if(x>)r=r/x*(x-);//如果x大于1，说明还有一个质因子没有除掉

     return r;//返回个数

 }

 int main(){

     int n;

     while(cin>>n&&n)

         cout<<Euler(n)<<endl;

     return ;

 }

巴特西

U - Relatives（欧拉函数）

Description

Input

Output

最新文章

热门文章