当前位置：首页 > 资讯 > 技术文档

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

时间：2022-05-01 02:24 编辑：来源：阅读：
扫一扫，手机访问

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

[b]一、快速幂[/b] 其实就是求[code]（a^b）% p[/code] ,（其中a,b,p都比较大在int范围内）这类问题。首先要知道取余的公式： [code]（a*b）%p=（a%p*b%p）%p [/code]。那么幂不就是乘机的累积吗，由此给出代码：

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);

}

[b]二、大数取模[/b] 它的原理就是这个取余公式： [code]（a+b）%p=(a%p+b%p)%p;[/code] 那么大数可以看做每一位的那位数字乘以自身的权然后每位相加。如：12345678=（1*10000000）+（2*1000000）+…+8。 [b]代码如下：[/b]

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;

} }

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

全部评论(0)

上一篇：VC++实现选择排序算法简单示例
下一篇：linux下access函数的用法介绍

资讯排行榜
更多>>