首页 > 代码库 > 快速幂+大数取模
快速幂+大数取模
快速幂,其实就是求(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;
} }
快速幂+大数取模
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。