一、快速幂
其实就是求(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;
} }
|
三、总结
以上就是本文的全部内容,希望对大家的学习和工作能有所帮助。如果有疑问可以留言交流。