d219 - 00374 - Big Mod

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算 B 的 P 次方模 M 的結果，即 R = B^P mod M。由於 B、P、M 的值可能很大，需要一個有效率的演算法來計算。

解題思路

這題可以使用模冪運算 (Modular Exponentiation) 來解決。模冪運算的核心思想是利用以下性質：

• (a * b) mod m = ((a mod m) * (b mod m)) mod m
• a^(2k) mod m = (a^k mod m)^2 mod m
• a^(2k+1) mod m = (a^k mod m)^2 * a mod m

透過遞迴地將 P 分成更小的子問題，並利用上述性質，可以有效地計算出 B^P mod M 的結果。程式碼中 mod 函數實現了這個遞迴過程。首先，如果 P 為 0，則返回 1。如果 P 為 1，則返回 B mod M。否則，判斷 P 是否為奇數，如果是，則計算 (a^(P/2) mod m)^2 * a mod m。如果 P 為偶數，則計算 (a^(P/2) mod m)^2 mod m。

複雜度分析

• 時間複雜度: O(log P)
• 空間複雜度: O(log P)

程式碼

#include <iostream>
using namespace std;
long long int bm;
inline long long int mod(long long int b,long long int p,long long int m){
	if(p==0)return 1;
	if(p==1)return bm;
	bool o=p&1;
	p>>=1;
	long long int tmp=mod(b,p,m);
	if(o)
		return tmp*tmp*b%m;
	else
		return tmp*tmp%m;
}
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	long long int b,p,m;
	while(cin >> b >> p >> m){
		bm=b%m;
		cout << mod(b,p,m) << "\n";
	}
}