快速幂

---

其实快速幂很简单，
只需将一个幂拆解即可。

• 例：

  $A^b =(A^{b/2})^2 = ((A^{b/4})^2)^2 = ······$ 直到指数为0

所以当 $b \equiv 0 \pmod{2}$ 时可以得到以下代码：

    long long qpow(int a, int b) {
	    if (b == 0) return 1;//当指数为0返回1
	    return qpow(a, b >> 1) * qpow(a, b >> 1);//返回1/2指数的平方
    }

• 注 ：$b>>1$ 可视为 $b/2$

那如果 $b \equiv 1 \pmod{2}$ 怎么办呢？
只需将 $A^b$ 转换为 $A*A^{b-1}$就行了

于是，我们便得出核心代码

    long long qpow(int a, int b) {
	    if (b == 0) return 1;//当指数为0返回1
	    if (b % 2 == 1) return a * qpow(a, b - 1);//若指数 b % 2 == 1 返回a*a^(b-1);
	    return qpow(a, b >> 1) * qpow(a, b >> 1);//返回1/2指数的平方
    }

整理代码：

    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll a, b;
    
    ll qpow(int a, int b) {
    	if (b == 0) return 1;//当指数为0返回1
	    if (b % 2 == 1) return a * qpow(a, b - 1);//若指数 b % 2 == 1 返回a*a^(b-1);
	    return qpow(a, b >> 1) * qpow(a, b >> 1);//返回1/2指数的平方
    }
    
    int main() {
    	cin >> a >> b;// 输入a,b 快速计算a^b
    	cout << qpow(a, b);
    	return 0;
    }