C++快速幂与大数取模算法示例

概述一、快速幂其实就是求（a^b）%p,（其中a,b,p都比较大在int范围内）这类问题。

一、快速幂

其实就是求（a^b）% p,（其中a,b,p都比较大在int范围内）这类问题。

首先要知道取余的公式： （a*b）%p=（a%P*b%p）%p 。

那么幂不就是乘机的累积吗，由此给出代码：

int fast(int a,int b,int p){  long long a1=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。

代码如下：

char s[200];#define mod 10000010;int main(){  while(gets(s)){  int k=strlen(s),sum=0; for(int i=0;i<k;i++) sum=(sum*10+s[i]-'0')%mod;  /当然要是担心sum还可能溢出，那就对里边再拆开来取余 cout<<sum<<endl;} }

三、总结

以上就是本文的全部内容，希望对大家的学习和工作能有所帮助。如果有疑问可以留言交流。

总结

以上是内存溢出为你收集整理的C++快速幂与大数取模算法示例全部内容，希望文章能够帮你解决C++快速幂与大数取模算法示例所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。