題目描述

給定三個正整數 N,M,P，求

輸入描述

第?1?行為一個整數?T，表示測試數據數量。

接下來的?T?行每行包含三個正整數?N,M,P。

輸出描述

輸出共?T?行，每行包含一個整數，表示答案。

輸入輸出樣例

示例 1

輸入

3
2 3 7
4 5 6
5 2 9

?

輸出

1
4
7

思想：

快速冪（Fast Exponentiation）是一種用于高效計算大整數冪運算的算法，特別是在計算?時非常有用。它的核心思想是通過分治法和二進制分解，將冪運算的時間復雜度從?O(b)?降低到O(logb)。

---

快速冪的核心思想

1. 二進制分解：

   • 將指數?b?表示為二進制形式。例如，b=13的二進制表示為?1101。

   • 通過二進制分解，可以將??分解為多個?a?的冪的乘積。例如：

     

     其中，8,4,1是二進制位為 1 的位置對應的冪。

2. 分治法：

   • 通過不斷平方?a，可以快速計算出??等冪。

   • 每次平方操作將冪的次數翻倍，從而大大減少計算量。

3. 模運算優化：

   • 在計算過程中，每一步都對結果取模?p，避免數值過大，同時保證結果的正確性。

---

快速冪的步驟

1. 初始化結果?res=1。

2. 檢查指數?b?的二進制位：

   • 如果當前二進制位為 1，將當前的?a?乘到結果?res?中，并對?p?取模。

   • 將?a?平方，并對?p?取模，為下一次循環做準備。

   • 將?b?右移一位（相當于?b=b/2），繼續處理下一位。

3. 當?b?變為 0 時，返回結果?res。

解題代碼：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;// 定義一個快速冪函數 qmi，用于計算 a^b % p
ll qmi(ll a, ll b, ll p)
{ll res = 1; // 初始化結果為 1while (b) // 當 b 不為 0 時循環{if (b & 1) // 如果 b 的最低位是 1res = res * a % p; // 將當前的 a 乘到結果中，并取模 pa = a * a % p; // 將 a 平方，并取模 pb >>= 1; // 將 b 右移一位，相當于 b /= 2}return res; // 返回最終結果
}int main()
{int t; // 定義測試用例的數量 tcin >> t; // 輸入測試用例的數量for (int i = 1; i <= t; i++) // 循環處理每個測試用例{ll n, m, p; // 定義三個正整數 n, m, pcin >> n >> m >> p; // 輸入 n, m, pcout << qmi(n, m, p) << '\n'; // 調用 qmi 函數計算 n^m % p 并輸出結果}return 0; // 程序正常結束
}

?

?

?

?

?

?

?

?