Relatives

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 16186		Accepted: 8208

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

Sample Output

6

4

Source

POJ 2407：Relatives（欧拉函数模板）

欧拉函数模板题

AC代码

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <limits.h>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#include <set>

#include <string>

#define ll long long

#define ms(a) memset(a,0,sizeof(a))

#define pi acos(-1.0)

#define INF 0x3f3f3f3f

const double E=exp(1);

using namespace std;

const int maxn=1e6+10;

int a[maxn];

int b[maxn];

//欧拉函数公式：

//φ(N)=N*(1-1/P1)*(1-1/P2)*...*(1-1/Pn).

int main(int argc, char const *argv[])

{

	int n;

	while(cin>>n&&n)

	{

		ms(b);

		ll ans=n;

		int vis=n;

		for(int i=2;i*i<=vis;i++)

		{

			if(vis%i==0)

			{

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

				while(vis%i==0)

				{

					vis/=i;

				}

			}

		}

		if(vis>1)

			ans=ans/vis*(vis-1);

		cout<<ans<<endl;

	}

	return 0;

}

// 两种求欧拉函数的方法：

//

// ******************第一种直接求解****************

// long long Euler(long long x)

// {

//     int res = x,a = x;

//     for(int i=2;i*i<=a;i++)

//     {

//         if(a%i==0)

//         {

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

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

//         }

//     }

//     if(a>1)res =res/a*(a-1);//res -= res/a;

//     return res;

// }

 // ******************第二种打表求解****************

// #define Max 1000001

// int euler[Max];

// void Euler()

// {

//      euler[1]=1;

//      for(int i=2;i<Max;i++)

//        euler[i]=i;

//      for(int i=2;i<Max;i++)

//         if(euler[i]==i)

//            for(int j=i;j<Max;j+=i)

//               euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出

// }

秒客网