euler函数.cpp

Euler函数: m = p1^r1 * p2^r2 * …… * pn^rn ai >= 1 , 1 <= i <= n Euler函数： 定义：phi(m) 表示小于等

/**********************
	Euler函数: 
m = p1^r1 * p2^r2 * …… * pn^rn ; ai >= 1 , 1 <= i <= n ;
Euler函数：
定义：phi(m) 表示小于等于m并且与m互质的正整数的个数。
			phi(m) = p1^(r1-1)*(p1-1) * p2^(r2-1)*(p2-1) * …… * pn^(rn-1)*(pn-1) ;
				  = m*(1 - 1/p1)*(1 - 1/p2)*……*(1 - 1/pn) ;
				  = p1^(r1-1)*p2^(r2-1)* …… * pn^(rn-1)*phi(p1*p2*……*pn) ;
定理：若(a , m) = 1 ; 则有 a^phi(m) = 1 (mod m) ;即a^phi(m) - 1 整出m 

在实际代码中可以用类似素数筛法求出
	for (i = 1 ; i < MAXN ; i++)
		phi[i] = i;
	for (i = 2 ; i < MAXN ; i++)
		if (phi[i] == i) 
		{
			for (j = i ; j < MAXN ; j += i) 
			{
				phi[j] /= i;
				phi[j] *= i - 1;
			}
		}

容斥原理：定义phi(p) 为比p小的与p互素的数的个数
设n的素因子有p1, p2, p3, … pk
包含p1, p2…的个数为n/p1, n/p2…
包含p1*p2, p2*p3…的个数为n/(p1*p2)…
phi(n) = n - sigm_[i = 1](n/pi) + sigm_[i!=j](n/(pi*pj)) - …… +- n/(p1*p2……pk) ;
	   = n*(1 - 1/p1)*(1 - 1/p2)*……*(1 - 1/pk) ;

**********************/
#include<iostream>
#include<cmath>
using namespace std;
const int MAX = 1000001; 

int prime[MAX] , pnum ; 

void Get_prime()	//素数筛选 
{
	bool bu[MAX] = {false};
	int i , j ;
	for(i = 2 ; i <= sqrt(MAX) ; i++)
	{
		if(!bu[i])
		{
			for(j = i*2 ; j <= MAX ; j += i)
				bu[j] = true ;
		}
	}
	pnum = 0 ;
	for(i = 2 ; i <= MAX ; i++)
		if(!bu[i])
			prime[pnum++] = i ;
}

int mypow(int a, int b) 
{ 
    int ans = 1; 
    while (b --) 
    { 
        ans *= a; 
    } 
    return ans; 
} 

int Euler(int n) //欧拉函数，即为小于n 并且与n 互质的数的个数.
{ 
    int i , t , p = 0; 
	int a[80] , b[80] ;
    for (i = 0; i < pnum ; ++ i) 
    { 
        t = prime[i]; 
        if (t * t > n) 
            break; 
        if (n % t == 0) 
        { 
            a[p] = t; 
            b[p] = 0; 
            while (n % t == 0) 
            { 
                n /= t; 
                b[p] ++; 
            } 
            p ++; 
        } 
    } 
    if (n > 1) 
    { 
        a[p] = n; 
        b[p++] = 1; 
    } 

    int ans = 1; 
    for (i = 0; i < p; ++ i) 
        ans *= mypow(a[i], b[i]-1)*(a[i]-1); 

    return ans; 
} 

int main()
{
	Get_prime() ;
	int n ;
	while(1 == scanf("%d" , &n))
	{
		if(n == 0) break;
		printf("%d\n" , Euler(n)) ;
	}
	return 0 ;
}