快速冪計算 （簡單計算器）

輸入

第一行輸入n,表示接下來要輸入n組；

接下來n行，分別三個，a, b, s, 分別表示要操作的兩個數，和操作符號，比如1 2 +，表示1+2，2 1000000000 ^，表示2的1000000000次方；

因為結果可能很大，所以都要與1000000007取模再輸出；

輸出

輸出計算結果，用換行隔開；

C++程式碼

#include<iostream>
#define ll long long
using namespace std;
ll p = 1000000007;
ll quickpow(ll a, ll b) {
	ll ans = 1;
	while (b) { 
		if (b & 1) ans = ans * a % p;
		a = a * a % p, b = b >> 1;
	}return ans % p;
}

int main() {
	int i;
	cin >> i;
	while (i) {
		ll a, b;
		char s;
		cin >> a >> b >> s;
		if (s == '+') cout << (a % p + b % p) % p << endl;
		if (s == '-') cout << (a % p - b % p) % p << endl;
		if (s == '*') cout << ((a % p) * (b % p)) % p << endl;
		if (s == '^') cout << quickpow(a, b) << endl;
		i--;
	}return 0;
}

---

這裡重要的是求冪運算，如果是按照常規方法，求冪就是不停的乘自身，複雜度是O(n)，通過快速冪，複雜度降為對數級。

在這裡關鍵的是指數b的移位元運算，b=b>>1，就是將二進位制的b向右邊移動一位，舉個例子，2的11次方，11的二進位制是1011，那2的11次方，就是2的二進位制的1011次方，就是2的（8+2+1）次方，其中8，2，1就是二進位制的位置的數，根據冪指數運演演算法則，2^(11)=2^(8+2+1)=2^8*2^2*2^1，相乘的數之間具有規律，都是前一個數位的平方，只要該數在該二進位制位是1，這裡就要乘以對應的數，每乘一次，二進位制b就右移動一位，當b右移到為0，就退出，乘積結束，這就是快速冪的數學原理。