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

时间:2022-09-24 15:46:23

一、快速幂

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

首先要知道取余的公式: (a*b)%p=(a%p*b%p)%p

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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。

代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
 
} }

三、总结

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