je pense, donc je suis
C++博客
|
首頁
|
發新隨筆
|
發新文章
|
聯系
|
聚合
|
管理
隨筆:34 文章:0 評論:32 引用:0
(a^b)%n迭代法實現
查了一下書,知道了這樣一個公式,這樣昨天二分法的疑問就可以解決了,也可以用迭代法實現了:看來吳文虎編寫的書還挺配套的.
也就是 a^b%n=((a^b-1)*a)%n====>(a*b)%n=((a%n)*b)%n===>a^b%n=(((a^(b/2))%n)*a^(b/2))%n
//
迭代法
int
modexp2(
int
a,
int
b,
int
n)
{
int
r;
r
=
a
%
n;
for
(
int
i
=
0
;i
<
b
-
1
;i
++
)
r
=
(r
*
a)
%
n;
return
r;
}
書中還說可以提高效率,研究后再說.
(a^b)%n=(a^(b/2)%n * a^(b/2)%n)%n
根據這個公式,討論奇數和偶數處理
int
modExp(
int
a,
int
b,
int
n)
{
int
d
=
1
,r
=
a;
while
(b)
{
if
(b
%
2
==
1
)
{d
=
d
*
r
%
n;}
r
=
r
*
r
%
n;
b
=
b
/
2
;
}
return
d;
}
發表于 2007-06-05 22:44
AIBPXTSHMF
閱讀(405)
評論(2)
編輯
收藏
引用
所屬分類:
Algorithm
評論
#
re: (a^b)%n迭代法實現
這個程序,一旦b是一個非常大的數,例如是100位的數的話,那這個程序運行的時間就太多了
要改進
int modexp2(int a,int b,int n)
{
int r,k=1,i;
r=a%n;
while(k!=b)
{
for(i=1;k+=i,i=i*2,k<b-1;)
r=(r*r)%n;
i=i/2;
}
return r;
}
這樣程序會快些
星夢情緣
評論于 2007-06-05 23:49
回復
更多評論
#
re: (a^b)%n迭代法實現
@ 星夢情緣呀!你和書上說的道理一樣!正在看呢!
AIBPXTSHMF
評論于 2007-06-06 07:28
回復
更多評論
刷新評論列表
只有注冊用戶
登錄
后才能發表評論。
【推薦】100%開源!大型工業跨平臺軟件C++源碼提供,建模,組態!
相關文章:
CodeGuru代碼閱讀(一)
Euclid擴展算法
(a^b)%n迭代法實現
(a^b)%n---ACM例題的疑惑
Least Common Mutiple
Greatest Common Divisor
mergesort優化若干證明
MERGESORT
Divide and Conquer
INSERT-SORT
網站導航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
<
2025年6月
>
日
一
二
三
四
五
六
25
26
27
28
29
30
31
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
1
2
3
4
5
公告
失去的和得到的是相等的, 怎么做由你自己選擇。
常用鏈接
我的隨筆
我的評論
我參與的隨筆
留言簿
(5)
給我留言
查看公開留言
查看私人留言
隨筆分類
(34)
Algorithm(10)
(rss)
Assembly(1)
(rss)
C/CPlusPlus(11)
(rss)
English
(rss)
Mathematics
(rss)
Other(5)
(rss)
Philosophy(1)
(rss)
Scheme
(rss)
Thinking(3)
(rss)
WebDesign(3)
(rss)
隨筆檔案
(34)
2007年8月 (1)
2007年7月 (8)
2007年6月 (8)
2007年5月 (1)
2007年4月 (2)
2007年3月 (5)
2007年2月 (1)
2007年1月 (8)
相冊
Book
lifeBelong
techpic
Friends
Stone的博客
愛砂July
虎子的博客
周波的博客
My Blog
szhoftuncun@csdn.net
szhoftuncun@cublog.cn
szhoftuncun@weiqi.cn
NBlog
Boost文檔翻譯
C++羅浮宮
負暄瑣話
OpenSource
gforge
sourceforge
Philosophy
NewMind
PhilosophyEnclopedia
Philosophypages
ProblemSet
SaratovStateUniversity
SITES
Bjarne Stroustrup
Haskell
Lambda the ultimate
reddit
筆記流年AboutHaskell
純粹物件導向空間
數學知識
最新隨筆
1.?最近有點浮躁
2.?GUI何去何從之WxWigets入門
3.?GUI何去何從之SmartWin++入門
4.?人的差異源于思考方式
5.?CodeGuru代碼閱讀(一)
6.?匯編學習筆記(一)
7.?軟件實習作業(二)
8.?女人為什么活得比男人累?
9.?夢與醒
10.?Linux分區若干
搜索
積分與排名
積分 - 26895
排名 - 692
最新隨筆
1.?最近有點浮躁
2.?GUI何去何從之WxWigets入門
3.?GUI何去何從之SmartWin++入門
4.?人的差異源于思考方式
5.?CodeGuru代碼閱讀(一)
6.?匯編學習筆記(一)
7.?軟件實習作業(二)
8.?女人為什么活得比男人累?
9.?夢與醒
10.?Linux分區若干
最新評論
1.?re: Euclid擴展算法
評論內容較長,點擊標題查看
--long
2.?re: GUI何去何從之WxWigets入門
評論內容較長,點擊標題查看
--Daniel King
3.?re: 最近有點浮躁
韜光養晦呀,呵呵
--秦歌
4.?re: 整型數組長度問題
今天我也遇到了同樣的問題,也上網查了些資料。..
當然,得到的,很多都是錯誤的,后來無奈,跟你用了一樣的方法...
不知道有誰能有更簡便的方法求出整型數組的長度..
--linymxp
5.?re: Euclid擴展算法
你改成cout<<x<<'\t'<<y<<'\t'<<extEuclid(a,b,x,y)<<endl;就行了。
--123
閱讀排行榜
1.?xml解析出現符號錯誤?(3909)
2.? 整型數組長度問題(3062)
3.?GUI何去何從之SmartWin++入門(2674)
4.?GUI何去何從之WxWigets入門 (1804)
5.?回車與換行的區別(1248)
評論排行榜
1.?最近有點浮躁(5)
2.?(a^b)%n---ACM例題的疑惑(5)
3.? 整型數組長度問題(4)
4.?Linux分區若干(3)
5.?人的差異源于思考方式(3)
Powered by:
博客園
模板提供:
滬江博客
Copyright ©2025 AIBPXTSHMF
久久99国产精品99久久
|
亚洲精品无码久久不卡
|
久久国产亚洲高清观看
|
久久这里只有精品首页
|
久久久久亚洲AV成人网人人网站
|
国产精品欧美亚洲韩国日本久久
|
伊人伊成久久人综合网777
|
久久婷婷五月综合97色
|
久久最新免费视频
|
99久久久国产精品免费无卡顿
|
伊人久久大香线蕉综合热线
|
一本久久精品一区二区
|
99re久久精品国产首页2020
|
久久青青草原精品国产软件
|
www.久久热
|
久久棈精品久久久久久噜噜
|
无码8090精品久久一区
|
99久久精品免费国产大片
|
久久精品国产亚洲av影院
|
亚洲国产视频久久
|
久久黄视频
|
国产精品永久久久久久久久久
|
久久99精品久久久久久动态图
|
国产精品久久久天天影视香蕉
|
av色综合久久天堂av色综合在
|
狠狠色伊人久久精品综合网
|
国产亚洲欧美成人久久片
|
久久精品欧美日韩精品
|
久久福利资源国产精品999
|
久久久久亚洲精品天堂久久久久久
|
精品无码久久久久久午夜
|
久久夜色精品国产欧美乱
|
伊人久久精品无码av一区
|
日本高清无卡码一区二区久久
|
久久99精品综合国产首页
|
久久av无码专区亚洲av桃花岛
|
中文无码久久精品
|
亚洲国产精品久久久天堂
|
久久夜色精品国产网站
|
久久精品a亚洲国产v高清不卡
|
久久精品亚洲一区二区三区浴池
|