LintCode ：快速幂

题目

a^n％b，其中a，b和n都是32位的整数。

样例

例如2^31％3 = 2

例如100^1000％1000 = 0

思路

首先我们知道这样一个公式 anmodb = (amodb)nmodb ; 也就是说一个数的因子取余之后相乘再取余与这个数取余相等。 那么为了防止溢出我们首先将a取余。之后每次相乘的结果也同样取余。

这样处理之后虽然我们可以防止溢出但是，本身的时间复杂度并没有得到改变，想要减少时间复杂度这里使用的是快速幂的方法。 如果b是偶数，那么 (a2)n/2modb = anmodb ； 如果b是奇数，那么 (a2)n2∗a = anmodb ;

代码

int fastPower(int a, int b, int n) { long long ans = 1; long long _a = a; _a = _a % b; if(n == 0) return 1 % b; while(n > 0) { if(n % 2 == 1) ans = (ans * _a) % b; n = n / 2; _a = (_a * _a) % b; } return ans; }

（这里因为题目给的a是int类型的，但是在计算a*a的时候由于b太大，所以会溢出，所以在代码中将a赋值给long long类型的_a）