快速幂 c++

一般大家写都是这样：

int ans = 1;
for (int i = 1; i <= a; i ++)
    ans *= x;

时间复杂度

但是，这对于我们还不够！我们要

---

首先我们得知道一个数学知识：

那么求  ，就有以下递归式：

如果 a 能被2整除（为偶）

   

如果 a 不能被2整除 （为奇）

      (这里a/2是整除)

每次求都先求调用 ， 不就是么？

最后补充一个东西：

  (i + j = a)

我们这里一边乘一边模，可以防止运行时超出 longlong

---

代码：

#include 
using namespace std;
typedef long long LL;
LL a, b, m;
//m是取模的数
LL q_pow(LL a, LL b, LL m) {
	if(b == 0)
		return 1;
	LL tmp = q_pow(a, b >> 1, m) % m;
	return (b & 1 ? a : 1) * tmp % m * tmp % m;
//b & 1 和 b % 2 == 1 是等价的
}
int main() {
	cin >> a >> b >> m;
	cout << q_pow(a, b, m);
	return 0;
} 

---

 误区解答：

首先，这个在数学上

  不管a是偶是奇这个等式都成立

但是，在这题中我们的次数a是整数，如果为奇，那么就是一个小数了。

为了保证一直是整数，当a为奇时，我们必须写成