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)

-err