d219. 00374 - Big Mod C++題解（正常版與極致優化版）

Jul 12, 2024

基本版本

#include<bits/stdc++.h>
using namespace std;
int mod(int b,int p,int m){
	int r=1,nr=b%m;
	while(p>0){
		if(p&1) r=(r*nr)%m;
		nr=(nr*nr)%m, p=p>>1;
	}
	return (b>=0&&m>0)?r:-1;
}
int main(){
	int b,p,m;
	while(cin>>b>>p>>m) cout<<mod(b,p,m)<<endl;
}

程式碼說明

函數 mod

這個函數的功能是計算 b^p mod m 的值，也就是 b 的 p 次方對 m 取餘。

函數參數

b：要計算 p 次方的底數
p：要計算的 b 的次方
m：取餘的模數

函數返回值

如果 b 和 m 都是正整數，則返回 b^p mod m 的值
否則返回 -1

函數運作原理

這個函數使用二進位快速冪算法來計算 b^p mod m。二進位快速冪算法的基本思想是，將 p 分解為二進位表示，然後根據二進位表示來計算 b^p。

具體來說，函數首先將 r 初始化為 1，將 nr 初始化為 b % m。然後，函數進入一個循環，在循環中：

如果 p 的最低有效位為 1，則將 r 更新為 r * nr mod m
將 nr 更新為 nr * nr mod m
將 p 右移一位

循環結束後，r 就是 b^p mod m 的值。

int main() {
	int b, p, m;
	while (cin >> b >> p >> m) cout << mod(b, p, m) << endl;
}

這段程式碼首先從標準輸入讀取三個整數 b、p 和 m，然後將這些整數傳遞給函數 mod 來計算 b^p mod m 的值，最後將計算結果輸出到標準輸出。

舉例

假設 b = 2、p = 5 和 m = 7，那麼 mod(b, p, m) 的值應該是 4。

以下是程式碼的執行結果：

2 5 7
4

極致優化版

#include <cstdio> // 使用C標準I/O函數
using namespace std;

#pragma GCC optimize("O3,unroll-loops,no-stack-protector,fast-math")

inline int modExponentiation(int base, int exponent, int modulus) {
  if (modulus == 0) return -1; // 避免除以零
  int result = 1;
  base %= modulus; // 優化初始模數運算

  #pragma ivdep
  while (exponent > 0) {
    if (exponent & 1) {
      result = static_cast<long long>(result) * base % modulus; // 使用long long避免溢出
    }
    base = static_cast<long long>(base) * base % modulus; // 使用long long避免溢出
    exponent >>= 1;
  }
  return result;
}

int main() {
  int base, exponent, modulus;
  while (scanf("%d %d %d", &base, &exponent, &modulus) == 3) {
    printf("%d\n", modExponentiation(base, exponent, modulus));
  }
  return 0;
}

優化說明

1. 避免除以零

在原來的程式碼中，函數 mod 的第一行是 int r = 1, nr = b % m;。這行程式碼會將 b 對 m 取餘並存儲在 nr 中。但是，如果 m 為 0，則會發生除以零錯誤。

在優化後的程式碼中，函數 modExponentiation 的第一行是 if (modulus == 0) return -1;。這行程式碼會在 modulus 為 0 時返回 -1，從而避免除以零錯誤。

2. 優化初始模數運算

在原來的程式碼中，函數 mod 的第二行是 nr = b % m;。這行程式碼會將 b 對 m 取餘並存儲在 nr 中。

在優化後的程式碼中，base %= modulus; 這行程式碼將 base 對 m 取餘並存儲在 base 中。這樣可以避免在循環中重複進行模數運算。

3. 使用 long long 避免溢出

在原來的程式碼中，函數 mod 的循環中，有兩行程式碼是：

if (p & 1) r = (r * nr) % m;
nr = (nr * nr) % m;

這兩行程式碼可能會導致溢出，尤其是當 b、p 或 m 很大的時候。

在優化後的程式碼中，這兩行程式碼改寫為：

if (exponent & 1) {
  result = static_cast<long long>(result) * base % modulus; // 使用long long避免溢出
}
base = static_cast<long long>(base) * base % modulus; // 使用long long避免溢出

這兩行程式碼使用 static_cast<long long> 將 result 和 base 暫時轉換為 long long 類型，從而避免溢出。

4. 使用 inline 關鍵字

在優化後的程式碼中，函數 modExponentiation 使用了 inline 關鍵字。inline 關鍵字可以告訴編譯器將函數內聯到函數調用處，從而提高執行效率。

5. 使用 GCC 優化選項

在優化後的程式碼中，使用了 #pragma GCC optimize("O3,unroll-loops,no-stack-protector,fast-math") 指令。這個指令可以告訴 GCC 編譯器使用 O3 優化級別，並啟用一些特定的優化選項，例如循環展開、關閉堆棧保護器和啟用快速數學運算。

6. 使用 scanf 和 printf 函數

在優化後的程式碼中，使用了 scanf 和 printf 函數來讀取和輸出數據。scanf 和 printf 函數是 C 標準 I/O 函數，具有較高的執行效率。