隨筆:152 文章:0 評論:129 引用:0
Headacher
學(xué)習(xí)筆記,從一點(diǎn)一滴做起。
C++博客
首頁
發(fā)新隨筆
發(fā)新文章
聯(lián)系
聚合
管理
歐拉函數(shù)
E(x)表示比x小的且與x互質(zhì)的正整數(shù)的個(gè)數(shù)。
*若p是素?cái)?shù),E(p)=p-1。
*E(p^k)=p^k-p^(k-1)=(p-1)*P^(k-1)
證:令n=p^k,小于n的正整數(shù)數(shù)共有n-1即(p^k-1)個(gè),其中與p不質(zhì)的數(shù)共[p^(k-1)-1]個(gè)(分別為1*p,2*p,3*p...p(p^(k-1)-1))。
所以E(p^k)=(p^k-1)-(p^(k-1)-1)=p^k-p^(k-1).得證。
*若ab互質(zhì),則E(a*b)=E(a)*E(b),歐拉函數(shù)是積性函數(shù).
*對任意數(shù)n都可以唯一分解成n=p1^a1*p2^a2*p3^a3*...*pn^an(pi為素?cái)?shù)).
則E(n)=E(p1^a1)*E(p2^a2)*E(p3^a3)*...*E(pn^an)
=(p1-1)*p1^(a1-1)*(p2-1)*p2^(a2-1)*...*(pn-1)*pn^(an-1)
=(p1^a1*p2^a2*p3^a3*...*pn^an)*[(p1-1)*(p2-1)*(p3-1)*...*(pn-1)]/(p1*p2*p3*...*pn)
=n*(1-1/p1)*(1-1/p2)*...*(1-1/pn)
* E(p^k) =(p-1)*p^(k-1)=(p-1)*p^(k-2)*p
E(p^(k-1))=(p-1)*p^(k-2)
->當(dāng)k>1時(shí),E(p^k)=E(p*p^(k-1))=E(p^(k-1))*p.
(當(dāng)k=1時(shí),E(p)=p-1.)
由上式: 設(shè)P是素?cái)?shù),
若p是x的約數(shù),則E(x*p)=E(x)*p.
若p不是x的約數(shù),則E(x*p)=E(x)*E(p)=E(x)*(p-1).
*快速求歐拉函數(shù)方法:
首先來回顧一下線性篩選素?cái)?shù)方法:
code
for
(i
=
2
;i
<=
1000000
;i
++
)
{
if
(
!
c[i])prime[len
++
]
=
i;
for
(j
=
0
;j
<
len
&&
prime[j]
*
i
<=
1000000
;j
++
)
{
c[prime[j]
*
i]
=
1
;
//
不是質(zhì)數(shù)
if
(i
%
prime[j]
==
0
)
break
;
//
}
}
}
然后求歐拉函數(shù):
Phi1
phi[
1
]
=
1
;
for
(i
=
2
; i
<
10000
; i
++
) {
if
(
!
mark[i]) {
phi[i]
=
i
-
1
;
continue
;
}
for
(j
=
0
; j
<
size
&&
prime[j]
*
prime[j]
<=
i; j
++
) {
if
(i
%
prime[j]
==
0
) {
if
(i
/
prime[j]
%
prime[j]
==
0
)
phi[i]
=
prime[j]
*
phi[i
/
prime[j]];
else
phi[i]
=
(prime[j]
-
1
)
*
phi[i
/
prime[j]];
break
;
}
}
}
由以上思想,可以在篩選素?cái)?shù)的過程中求出歐拉函數(shù):
Phi
for
(i
=
2
;i
<=
limit;i
++
)
{
if
(mark[i]
==
0
)
{
prime[
++
prime[
0
]]
=
i;
E[i]
=
i
-
1
;
}
for
(j
=
1
;j
<=
prime[
0
]
&&
prime[j]
*
i
<=
limit;j
++
)
{
mark[prime[j]
*
i]
=
1
;
if
(i
%
prime[j]
==
0
)
{
E[i
*
prime[j]]
=
E[i]
*
prime[j];
break
;
}
else
E[i
*
prime[j]]
=
E[i]
*
(prime[j]
-
1
);
}
}
發(fā)表于 2009-07-19 12:39
Headacher
閱讀(3141)
評論(0)
編輯
收藏
引用
所屬分類:
數(shù)據(jù)結(jié)構(gòu)和算法
只有注冊用戶
登錄
后才能發(fā)表評論。
【推薦】100%開源!大型工業(yè)跨平臺(tái)軟件C++源碼提供,建模,組態(tài)!
相關(guān)文章:
POJ 2043 掃描 計(jì)算幾何
POJ 1113 凸包
POJ 3164 最小樹形圖 朱劉算法
POJ 2761 SBT 靜態(tài)數(shù)組實(shí)現(xiàn)
POJ 2778 自動(dòng)機(jī)_矩陣乘法
HDU 2222 AC自動(dòng)機(jī)
數(shù)位統(tǒng)計(jì)
無恥IO優(yōu)化
哦哦
有上下界的可行流
網(wǎng)站導(dǎo)航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
CALENDER
<
2010年5月
>
日
一
二
三
四
五
六
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
公告
留言簿
(8)
給我留言
查看公開留言
查看私人留言
隨筆分類
ACM-ICPC(7)
(rss)
操作系統(tǒng)
(rss)
計(jì)算機(jī)組成與體系結(jié)構(gòu)(2)
(rss)
數(shù)據(jù)結(jié)構(gòu)和算法(34)
(rss)
數(shù)據(jù)庫
(rss)
心情日記(20)
(rss)
隨筆檔案
2010年12月 (1)
2010年9月 (1)
2010年5月 (3)
2010年4月 (3)
2010年3月 (1)
2010年2月 (2)
2010年1月 (10)
2009年12月 (1)
2009年10月 (3)
2009年9月 (6)
2009年8月 (14)
2009年7月 (8)
2009年6月 (2)
2009年5月 (17)
2009年4月 (4)
2009年3月 (5)
2009年2月 (25)
2009年1月 (9)
2008年12月 (1)
2008年11月 (30)
2008年10月 (4)
2008年7月 (2)
ACM Teammates
Qinz
(rss)
SHFACM
(rss)
wudired
(rss)
The One
May
(rss)
搜索
積分與排名
積分 - 134582
排名 - 193
最新評論
1.?re: POJ 1379 run away 模擬退火算法[未登錄]
為何按你的代碼交會(huì)RE呢?
--zhang
2.?re: POJ 1947 樹狀dp[未登錄]
評論內(nèi)容較長,點(diǎn)擊標(biāo)題查看
--Sky
3.?re: 獨(dú)立集,覆蓋集,支配集,最大團(tuán),最大匹配
評論內(nèi)容較長,點(diǎn)擊標(biāo)題查看
--fly2best
4.?re: HDU HDOJ 1004 Let the Balloon Rise 字典樹[未登錄]
尼瑪 這就是個(gè)水題
--xxx
5.?re: nuaa 1017 最大0,1子矩陣[未登錄]
1 0 1 0 1
2 1 2 1 2
3 2 2 2 0
0 3 4 3 1
1 0 5 4 2 這個(gè)寫錯(cuò)了吧
第三行第三列那個(gè)2應(yīng)該為3才對
--hu
閱讀排行榜
1.?獨(dú)立集,覆蓋集,支配集,最大團(tuán),最大匹配(7939)
2.?原碼 補(bǔ)碼 反碼 移碼(6422)
3.?POJ 計(jì)算幾何入門題目推薦(轉(zhuǎn))(5715)
4.?POJ 1379 run away 模擬退火算法(4422)
5.?數(shù)據(jù)的浮點(diǎn)數(shù)表示(3958)
評論排行榜
1.?POJ 1379 run away 模擬退火算法(12)
2.?我真是太笨了……(10)
3.?PKU POJ 2186 Popular Cows 強(qiáng)連通分量(5)
4.?HDU HDOJ 1005 Number Sequence(4)
5.?數(shù)論中的一些公式(轉(zhuǎn))(4)
Powered By:
博客園
模板提供
:
滬江博客
精品国产乱码久久久久久浪潮
|
久久国产三级无码一区二区
|
囯产极品美女高潮无套久久久
|
亚洲а∨天堂久久精品9966
|
伊人久久五月天
|
亚洲中文字幕久久精品无码喷水
|
婷婷久久精品国产
|
国内精品人妻无码久久久影院导航
|
蜜臀久久99精品久久久久久小说
|
亚洲中文字幕无码久久精品1
|
久久99精品久久久久子伦
|
国产高潮久久免费观看
|
国产高潮国产高潮久久久91
|
99久久成人18免费网站
|
国产精品成人久久久
|
韩国三级中文字幕hd久久精品
|
亚洲欧美成人综合久久久
|
99久久精品国产一区二区三区
|
欧美午夜精品久久久久久浪潮
|
亚洲va中文字幕无码久久
|
国内精品久久久久久不卡影院
|
亚洲国产精品无码久久
|
亚洲国产成人精品女人久久久
|
久久国产精品成人影院
|
国色天香久久久久久久小说
|
久久国产视屏
|
国产成人精品久久亚洲高清不卡
|
久久久久女人精品毛片
|
伊人色综合久久天天网
|
精品人妻久久久久久888
|
久久久久人妻一区二区三区
|
久久中文字幕视频、最近更新
|
久久久久久久亚洲精品
|
欧美一区二区精品久久
|
久久福利青草精品资源站免费
|
久久人人爽人人爽人人AV东京热
|
噜噜噜色噜噜噜久久
|
亚洲国产一成久久精品国产成人综合
|
久久青青草原综合伊人
|
国产高清国内精品福利99久久
|
亚洲国产精品久久久久
|