快速幂取模（分治思想）

快速幂取模

许多时候我们需要计算a^b %c 如是的式子。

 

一、像下面这样直接来求
int res = 1;
for(int i = 1;i<=b;i++)
{
res = res * a;
}
res = res % c;
如果b很大，很容易超时；如果a,b很大，在计算过程中可能会超过long long所能表示的范围，因此想办法优化。
二、对于取模运算有这样一个性质：a^b mod c =(a mod c)^b  mod c

于是改进一下：
int res = 1;
a = a % c; //加上这一句
for(int i = 1;i<=b;i++)
{
res = (res * a) % c;//这里再取了一次余
}
res = res % c;
这样能避免超数范围的问题，但时间复杂度依旧是O(b)，当b很大依旧会爆时间。
三、只有对b处理，可能优化时间复杂度，有如下式子：
这里有一种分治的思想，实际上它的原理可以用二进制来理解：
比如说我要计算 5^7,7的二进制为111,7可以写成1*2^2+1*2^1+1*2^0 ,5^7=5^(1*2^2+1*2^1+1*2^0),于是可以分别计算5^4 ,5^2,5^1,再对4,2,1作类似的处理。

代码示例

int FastExp(int a,int b,int c)
{
int res=1;
a=a%c;
while(b>0)
{
if(b&1) //二进制b为奇数时，最后一位是1
res=(a*res)%c;
b=b>>1; //二进制右移1位，相当于对下取整除2
a=(a*a)%c;
}
return res;
}

 

例题：
总时间限制:
1000ms
内存限制:
65536kB

描述
已知长度最大为200位的正整数n，请求出2011^n的后四位。

 

输入
第一行为一个正整数k，代表有k组数据，k<=200接下来的k行，

每行都有一个正整数n，n的位数<=200
输出
每一个n的结果为一个整数占一行，若不足4位，去除高位多余的0

 

样例输入
3
5
28
792
样例输出
1051
81
5521

代码示例
#include<bits/stdc++.h>
using namespace std;

int FastExp(int a,int b,int c)
{
int res=1;
a=a%c;
while(b>0)
{
if(b&1) //二进制b为奇数时，最后一位是1
res=(a*res)%c;
b=b>>1; //二进制右移1位，相当于对下取整除2
a=(a*a)%c;
}
return res;
}

long long BignumMod(char *s,int mod)
{
long long ans=0;
for(int i=0;s[i]!=’\0′;++i){
ans=(ans*10+s[i]-’0′)%mod;
}
return ans;
}

int main()
{

//freopen(“C://Users//Francis//Desktop//对拍//date.txt”,”r”,stdin);
//freopen(“C://Users//Francis//Desktop//对拍//out1.txt”,”w”,stdout);
int k,ans;
long long n;
char str[210];
cin>>k;
while(k–)
{
cin>>str;
n=BignumMod(str,500);
ans=FastExp(2011,n,10000);
cout<<ans<<endl;
}
return 0;
}
其中涉及到了大数取模，可以参看我的另一篇文章：

http://blog.csdn.net/feynman1999/article/details/59117616