C++快速幂与大数取模算法示例
一、快速幂
其实就是求（a^b）%p,（其中a,b,p都比较大在int范围内）这类问题。
首先要知道取余的公式：（a*b）%p=（a%p*b%p）%p。
那么幂不就是乘机的累积吗，由此给出代码：
intfast(inta,intb,intp)
{longlonga1=a,t=1;
while(b>0)
{if(b&1)/如果幂b是奇数多乘一次，因为后边会除2变偶数，（7/2=3）
t=(t%p)*(a1%p)%p;
a1=(a1%p)*(a1%p)%p;
b/=2;}
return(int)(t%p);
}
二、大数取模
它的原理就是这个取余公式：（a+b）%p=(a%p+b%p)%p;
那么大数可以看做每一位的那位数字乘以自身的权然后每位相加。
如：12345678=（1*10000000）+（2*1000000）+…+8。
代码如下：
chars[200];
#definemod10000010;
intmain()
{while(gets(s))
{intk=strlen(s),sum=0;
for(inti=0;i<k;i++)
sum=(sum*10+s[i]-'0')%mod;/当然要是担心sum还可能溢出，那就对里边再拆开来取余
cout<<sum<<endl;
}}
三、总结
以上就是本文的全部内容，希望对大家的学习和工作能有所帮助。如果有疑问可以留言交流。
热门推荐
10 生日祝福语朋友简短的话
11 宝贝的人生祝福语简短
12 新年有哪些祝福语简短
13 简短又洋气祝福语大全
14 简短祝福语除夕快乐英文
15 生日贺卡祝福语毕业简短
16 战友聚会祝福语幽默简短
17 最新中秋祝福语简短英语
18 夏日升学宴祝福语简短
