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)
標簽：
Euler
lt
phi
函數
上傳時間：
2014-01-10
上傳用戶：wkchong
