快速幂取模（分治思想）

2019-04-13 21:00发布

站内文章 / 模拟电子
16779 0 1292
快速幂取模 许多时候我们需要计算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 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]!='

热门文章