哪位大牛教教我快速幂怎么写？pascal、c、c++均可，要详细的注释_noip吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：18,540贴子：
哪位大牛教教我快速幂怎么写？pascal、c、c++均可，要详细的注释收藏
哪位大牛教教我快速幂怎么写？pascal、c、c++均可，要有详细的注释。
点我0元领取你的快充神器！
先转二进制，接着写就可以了
求代码。。。详细的。。要有注释的谢谢
代码我找不到了，讲一下思路。首先你要知道， (a * b) mod c = (a mod c) * (b mod c)
示例a41＝(a20)2·a，a20＝(a10)2，a10＝(a5)2，a5＝(a2)2·a，a2＝(a)2“a41”是a的41次方(1) 递归算法 long long quickpow(long long a, long long b) {
if (b == 0) return 1;
long long r=quickpow(a, b/2);
if (b%2) r*=a;
} (2) 非递归算法 long long quickpow(long long a, long long b) {
long long d=1, t=a;
while (b&0)
if (b%2) d=d*t;
类似的ab mod n代码如下： long long quickdiv(long long a, long long b, long long n) {
long long d=1, t=a;
while (b&0)
d=(d*t)%n;
t=(t*t)%n;
double pow = 1;while (index){if (index & 1)pow *=base *=index &&= 1;}
关键是要高精度（准确的说是指位运算）。。。你们打1000没一个过。。。爆了。。。（高精乘不用教，我会）
求大牛们注释+解释下位运算（不要直接贴baidu上搜的）
不要 a^b mod n 这种快速幂，求大牛们的回复
再次求大牛们解答
英国皇家道尔顿[Doulton]矽藻瓷滤水器两百年专注于水处理，享誉全球。
不懂LZ在说什么。。。高精度会？？？C++直接重载操作符一行代码不用改。。。
这种google一下一片一片的吧。。。。。。。。。。。。。。
直接问楼上的神犇、
伸手之前好歹搜搜吧。轻易说不懂干什么。如果这点自学能力都没有何苦搞竞赛。
解释一下递归算法，假设求a^41long long quickpow(long long a, long long b) { if (b == 0) return 1;
// a的0次方当然是1// 先说a^40// 如果想求a^40，那么最快的是求a^20，这样就缩小了规模// 因为20×2=40，所以利用a^20还能直接平方得a^40long long r=quickpow(a, b/2); // 然后因为a^20算出来了，所以直接平方，就是a^40r*=r; // 回到a^41// a^41=a^40×a，a^40在上面能算出来，但是还少个a// 下面就是把这个a乘上if (b%2) r*=a;
} 对于我来说，如果某算法没学明白，那么最简单的处理方法是——背除非NOIP让带代码模板。。。
突然想起来写过一个三分的快速幂。。。。速度很快。。。。。虽然代码长了一点。。。。。然后当时二逼了 又写了一个四分的快速幂。。。还惊讶了好半天为啥速度跟二分一样的。。。是我sb。。。
见 Pascal的那个times就是快速幂
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或快速幂_百度百科
本词条缺少名片图，补充相关内容使词条更完整，还能快速升级，赶紧来吧！
快速幂顾名思义，就是快速算某个数的多少次幂。其时间复杂度为 O(log?N)， 与朴素的O(N)相比效率有了极大的提高。
快速幂原理
以下以求a的b次方来介绍[1]
把b转换成。
该二进制数第i位的权为
11的二进制是1011
11 = 2?×1 + 2?×0 + 2?×1 + 2?×1
因此，我们将a??转化为算
快速幂实现
快速幂可以用这个强大的工具实现
b&and&1{也就是取b的二进制最低位(即第0位)　判断b是否为奇数，是则为1}&
b&shr&1{就是去掉b的二进制最低位(即第0位)}&
有了这个强大的工具，快速幂就好实现了！
以下为pascal的实现：
var&a,b,n:int64;
function&f(a,b,n:int64):int64;
var&t,y:int64;
&&t:=1;&y:=a;
&&while&b&&0&do&begin
&&&&if(b&and&1)=1&then&t:=t*y&mod&n;
&&&&y:=y*y&mod&n;{这里用了一个很强大的技巧,y*y即求出了a^(2^(i-1))不知道这是什么的看原理&
&&&&&&&&&&&&&&&&&&&&a^(2^(i-1))*a^(2^(i-1))=a^(2^i)
&&&&&&&&&&&&&&&&&&&&而且一般情况下a*b&mod&c&=(a&mod&c)*(b&mod&c)&mod&c}
&&&&b:=b&shr&1;{去掉已经处理过的一位}
&&exit(t);
&&read(a,b,n);{n是模}
&&writeln(f(a,b,n));
以下为C的实现，为了方便与pascal的对照，变量全部与上面相同.可以对照查看。
ll&pow(ll&a,ll&i)
&&&&if&(i==0)&return&1;
&&&&int&temp=pow(a,i&&1);
&&&&temp=temp*temp%MOD;
&&&&if&(i&1)&temp=(ll)temp*a%MOD;
&&&&return&temp%MOD;
非递归版：
&&&&ll&f(ll&a,ll&b,ll&n){
&&&&&&&&int&t,y;
&&&&&&&&t=1;&y=a;
&&&&&&&&while&(b!=0){
&&&&&&&&&&&&if&(b&1==1)&t=t*y%n;
&&&&&&&&&&&&y=y*y%n;&b=b&&1;
&&&&&&&&return&t;
快速幂代码比较
快速幂常规求幂
int&pow1(int&a,int&b)
&&&&int&r=1;
&&&&while(b--)
&&&&&&&&r*=a;
&&&&return&r;
快速幂二分求幂（一般）
int&pow2(int&a,int&b)
int&r=1,base=a;
while(b!=0)
&&&&if(b%2)
&&&&&&&&r*=
&&&&base*=
快速幂二分求幂（位操作，同pow2）
int&pow4(int&a,int&b)
&&&&int&r=1,base=a;
&&&&while(b!=0)
&&&&&&&&if(b&1)
&&&&&&&&&&&&r*=
&&&&&&&&base*=
&&&&&&&&b&&=1;
&&&&return&r;
快速幂快速求幂（位运算，更复杂）
int&pow3(int&x,int&n)
&&&&if(n==0)&return&1;
&&&&&&&&while((n&1)==0)
&&&&&&&&&&&&n&&=1;
&&&&&&&&&&&&x*=x;
&&&&int&result=x;
&&&&n&&=1;
&&&&while(n!=0)
&&&&&&&&x*=x;
&&&&if((n&1)!=0)
&&&&&&&&result*=x;
&&&&n&&=1;
&&&&return&
．新浪．[引用日期]1144人阅读
ACM_数论（12）
下面是一个快速幂的介绍：
先贴一个秦九韶算法（Horner算法）的原理：
设有项的次函数
将前项提取公因子，得
再将括号内的前项提取公因子，得
如此反复提取公因子，最后将函数化为
则即为所求
下面是讲解快速幂的：（By&&夜せ︱深 & 感谢作者）
快速幂取模算法
在网站上一直没有找到有关于快速幂算法的一个详细的描述和解释，这里，我给出快速幂算法的完整解释，用的是语言，不同语言的读者只好换个位啦，毕竟读的人较多
所谓的快速幂，实际上是快速幂取模的缩写，简单的说，就是快速的求一个幂式的模余。在程序设计过程中，经常要去求一些大数对于某个数的余数，为了得到更快、计算范围更大的算法，产生了快速幂取模算法。有读者反映在讲快速幂部分时有点含糊，所以在这里对本文进行了修改，作了更详细的补充，争取让更多的读者一目了然]
我们先从简单的例子入手：求a^b % c = ?
算法首先直接地来设计这个算法：
int&ans&=&1;
for(int&i&=&1;i&=b;i++)
ans&=&ans&*&a;
ans&=&ans&%&c;
这个算法的时间复杂度体现在循环中，为O（）.这个算法存在着明显的问题，如果和过大，很容易就会溢出。
那么，我们先来看看第一个改进方案：在讲这个方案之前，要先有这样一个公式：a^b%c=(a%c)^b%c.这个公式大家在离散数学或者数论当中应该学过，不过这里为了方便大家的阅读，还是给出证明：
引理：a^b%c = (a%c)^b%c
上面公式为下面公式的引理，即积的取余等于取余的积的取余。
证明了以上的公式以后，我们可以先让关于取余，这样可以大大减少的大小，
于是不用思考的进行了改进：
int&ans&=&1;
a&=&a&%&c;&//加上这一句
for(int&i&=&1;i&=b;i++)
ans&=&ans&*&a;
ans&=&ans&%&c;
聪明的读者应该可以想到，既然某个因子取余之后相乘再取余保持余数不变，那么新算得的也可以进行取余，所以得到比较良好的改进版本。
int&ans&=&1;
a&=&a&%&c;&//加上这一句
for(int&i&=&1;i&=b;i++)
ans&=&(ans&*&a)&%&c;//这里再取了一次余
ans&=&ans&%&c;
这个算法在时间复杂度上没有改进，仍为O(b)，不过已经好很多的，但是在过大的条件下，还是很有可能超时，所以，我们推出以下的快速幂算法。
快速幂算法依赖于以下明显的公式，我就不证明了。
那么我们可以得到以下算法：
int&ans&=&1;
a&=&a&%&c;
if(b%2==1)
ans&=&(ans&*&a)&mod&c;&//如果是奇数，要多求一步，可以提前算到中
k&=&(a*a)&%&c;&//我们取2而不是
for(int&i&=&1;i&=b/2;i++)
ans&=&(ans&*&k)&%&c;
ans&=&ans&%&c;
我们可以看到，我们把时间复杂度变成了O(b/2).当然，这样子治标不治本。但我们可以看到，当我们令时，状态已经发生了变化，我们所要求的最终结果即为b/2&mod&c而不是原来的b&mod&c，所以我们发现这个过程是可以迭代下去的。当然，对于奇数的情形会多出一项，所以为了完成迭代，当是奇数时，我们通过
ans&=&(ans&*&a)&%&c;来弥补多出来的这一项，此时剩余的部分就可以进行迭代了。
形如上式的迭代下去后，当时，所有的因子都已经相乘，算法结束。于是便可以在O（）的时间内完成了。于是，有了最终的算法：快速幂算法。
算法：快速幂算法
int&ans&=&1;
a&=&a&%&c;
while(b&0)
if(b&%&2&==&1)
ans&=&(ans&*&a)&%&c;
a&=&(a&*&a)&%&c;
将上述的代码结构化，也就是写成函数：
int&PowerMod(int&a,&int&b,&int&c)
int&ans&=&1;
a&=&a&%&c;
while(b&0)
if(b&%&2&=&=&1)
ans&=&(ans&*&a)&%&c;
a&=&(a&*&a)&%&c;
本算法的时间复杂度为O（），能在几乎所有的程序设计（竞赛）过程中通过，是目前最常用的算法之一。
以下内容仅供参考：
扩展：有关于快速幂的算法的推导，还可以从另一个角度来想。
=？&求解这个问题，我们也可以从进制转换来考虑：
将进制的转化成进制的表达式：
注意此处的要么为，要么为，如果某一项，那么这一项就是，这个对应了上面算法过程中是偶数的情况，为对应了是奇数的情况不要搞反了，读者自己好好分析，可以联系进制转进制的方法，我们从依次乘到。对于每一项的计算，计算后一项的结果时用前一项的结果的平方取余。对于要求的结果而言，为时不用把它乘起来，因为这一项值为，为项时要乘以此项再取余。这个算法和上面的算法在本质上是一样的，读者可以自行分析，这里我说不多说了，希望本文有助于读者掌握快速幂算法的知识点，当然，要真正的掌握，不多练习是不行的。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：38547次
积分：1959
积分：1959
排名：第16382名
原创：161篇
阅读：1813
(1)(4)(1)(2)(33)(6)(5)(9)(16)(17)(11)(14)(3)(20)(26)