輸入
第一行輸入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，就退出，乘積結束，這就是快速冪的數學原理，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/105355.html
標籤：其他
上一篇：爬蟲百度百萬高清美圖源代碼