啥是快速冪
快速冪，顧名思義，就是快速算某個數的多少次冪。其時間復雜度為 \(O(\log N)\)， 與樸素的\(O(N)\)相比效率有了極大的提高。
原理
來自學長：
我們可以把 \(b\) 分解成二進制數，其中從小到大每一個二進制位
是 \(b_1 ,b_2 ,...,b_{?\log b+1?}\) 。
根據二進制轉十進制的原理，\(b\) 的十進制表示是可以通過
\(b_1 ,b_2 ,...,b_{?\log b+1?}\) 的值在 \(O(\log n)\) 的時間內解出的。
這就啟發了我們可以用同樣的方法去算 \(a^b\) 。
計算\(a\)的\(b\)次冪\(a^b\),如果\(a\)為偶數顯然有\(a^b=(a^{\frac{b}{2}})^2\)，也就是說我們僅需要計算其\(b/2\)冪，然后平方即可，如果n為奇數可以寫成\(a^b=a\times (a^{\frac{b-1}{2}})^2\)，該方法可以迭代的進行，大大降低了計算所需的時間。
由于算出的數可能特別大，所以通常會在計算過程中對一個數取模，保證了不會爆掉，這樣的運算叫做快速冪取余運算
代碼實現
代碼實現比較簡潔，用上位運算速度還會快些，寫的時候最好都用long long來寫，不然有可能爆\(int\)
#define ll long long
ll power(ll a,ll b,ll c){ll res=1;while(b){if(b&1)//判斷二進制最后一位是否為1res=res*a%c;a=a*a%c;b>>=1;//每次除以2}return res%c;
}
)
