d636 - 大爆炸bomb
題目描述
題目要求計算 a 的 b 次方，並將結果模 10007 輸出。由於 a 和 b 的值可能很大，直接計算 a^b 會導致溢出，因此需要使用模運算來避免溢出。
解題思路
本題的核心是快速冪（Binary Exponentiation）演算法。快速冪是一種高效計算整數冪的方法，它利用了以下原理：
- 如果 b 是偶數，則 a^b = (a^(b/2))^2
- 如果 b 是奇數，則 a^b = a * (a^(b/2))^2
通過遞迴地應用這個原理，我們可以將計算 a^b 的次數減少到 log(b) 級別，從而避免了溢出和提高計算效率。
程式碼中 mod 函數實現了快速冪演算法，並在每次乘法運算後取模，以防止溢出。
複雜度分析
- 時間複雜度: O(log b)
- 空間複雜度: O(log b) (由於遞迴調用堆疊)
程式碼
#include <iostream>
using namespace std;
long long int bm;
inline long long int mod(long long int b,long long int p){
if(p==0)return 1;
if(p==1)return bm;
bool o=p&1;
p>>=1;
long long int tmp=mod(b,p);
if(o)
return tmp*tmp*b%10007;
else
return tmp*tmp%10007;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
long long int b,p;
while(cin >> b >> p){
bm=b%10007;
cout << mod(b,p) << "\n";
}
}