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
阅读(388)
评论(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;
}
这样程序会快些
#
re: (a^b)%n迭代法实现
@ 星梦情缘呀!你和书上说的道理一样!正在看呢!
刷新评论列表
只有注册用户
登录
后才能发表评论。
【推荐】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
管理
<
2007年6月
>
日
一
二
三
四
五
六
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
6
7
公告
失去的和得到的是相等的, 怎么做由你自己选择。
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(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分区若干
搜索
积分与排名
积分 - 26299
排名 - 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解析出现符号错误?(3901)
2. 整型数组长度问题(3028)
3. GUI何去何从之SmartWin++入门(2658)
4. GUI何去何从之WxWigets入门 (1776)
5. 回车与换行的区别(1232)
评论排行榜
1. (a^b)%n---ACM例题的疑惑(5)
2. 最近有点浮躁(5)
3. 整型数组长度问题(4)
4. Linux分区若干(3)
5. 人的差异源于思考方式(3)