快速幂(fast power)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**************************************************************** 
 * Description: C++ implementation of fast power  快速幂 luogu P1226
 * Author: Alex Li
 * Date: 2023-07-24 19:48:43
 * LastEditTime: 2024-02-02 07:48:28
****************************************************************/
#include <iostream> // 引入输入输出流库
using namespace std; // 使用标准命名空间

int a, b, p, result; // 声明全局变量a（底数），b（指数），p（模数），result（结果）

int main(){
    cin >> a >> b >> p; // 从标准输入读取底数a，指数b和模数p

    result = 1; // 初始化结果为1，因为任何数的0次幂都是1

    while (b) { // 当b不为0时执行循环
        if (b % 2 == 1) { // 如果b是奇数
            result = (result * a) % p; // 更新result为result与a的乘积对p取模
            b /= 2; // 将b除以2，进行下一轮计算
            a = (a * a) % p; // 将a更新为a的平方对p取模
        } else { // 如果b是偶数
            b /= 2; // 将b除以2，进行下一轮计算
            a = (a * a) % p; // 将a更新为a的平方对p取模
        }
    }
    cout << result << endl; // 输出最终的计算结果
    return 0; // 程序正常结束
}