Euler函數(shù):
m = p1^r1 * p2^r2 * …… * pn^rn ai >= 1 , 1 <= i <= n
Euler函數(shù)：
定義：phi(m) 表示小于等于m并且與m互質(zhì)的正整數(shù)的個(gè)數(shù)。
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
在實(shí)際代碼中可以用類似素?cái)?shù)篩法求出
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互素的數(shù)的個(gè)數(shù)
設(shè)n的素因子有p1, p2, p3, … pk
包含p1, p2…的個(gè)數(shù)為n/p1, n/p2…
包含p1*p2, p2*p3…的個(gè)數(shù)為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)
標(biāo)簽：
Euler
lt
phi
函數(shù)
上傳時(shí)間：
2014-01-10
上傳用戶：wkchong
Instead of finding the longest common
subsequence, let us try to determine the
length of the LCS.
Then tracking back to find the LCS.
Consider a1a2…am and b1b2…bn.
Case 1: am=bn. The LCS must contain am,
we have to find the LCS of a1a2…am-1 and
b1b2…bn-1.
Case 2: am≠bn. Wehave to find the LCS of
a1a2…am-1 and b1b2…bn, and a1a2…am and
b b b
b1b2…bn-1
Let A = a1 a2 … am and B = b1 b2 … bn
Let Li j denote the length of the longest i,g g
common subsequence of a1 a2 … ai and b1 b2
… bj.
Li,j = Li-1,j-1 + 1 if ai=bj
max{ L L } a≠b i-1,j, i,j-1 if ai≠j
L0,0 = L0,j = Li,0 = 0 for 1≤i≤m, 1≤j≤n.
標(biāo)簽：
the
subsequence
determine
Instead
上傳時(shí)間：
2013-12-17
上傳用戶：evil
//初始化
initscr()
//獲得屏幕尺寸
getmaxyx(stdscr, h, w)
//畫(huà)背景
for(i=0 i<h i++)
for(j=0 j<w j++){
mvaddch(i, j, ACS_CKBOARD)
}
refresh()
//建立窗口
pad = newpad(80, 128)
for(i=0 i<80 i++){
char line[128]
sprintf(line, "This line in pad is numbered d\n", i)
mvwprintw(pad, i, 0, line)
}
//刷新屏幕
refresh()
prefresh(pad, 0, 1, 5, 10, 20, 45)
for(i=0 i<50 i++){
prefresh(pad, i+1, 1, 5, 10, 20, 45)
usleep(30000)
}
//等待按鍵
getch()
標(biāo)簽：
getmaxyx
initscr
stdscr
for
上傳時(shí)間：
2014-08-30
上傳用戶：龍飛艇
