题解 | 乘方取模
乘方取模
https://www.nowcoder.com/practice/40ae98fd382e407081a530f0c2ef2cdb
解题思路
-
基本思路：
- 使用快速幂算法计算
。
- 通过二进制拆分指数
来减少计算次数。
- 在计算过程中同时进行取模运算，避免溢出。
- 使用快速幂算法计算
-
实现方法：
- 将指数
- 根据二进制位为1的位置进行累乘。
- 每次乘法后立即取模，保证中间结果不会溢出。
- 将指数
代码
#include <iostream>
using namespace std;
long long quick_pow_mod(long long a, long long b, long long m) {
long long result = 1;
a %= m; // 先对a取模
while (b > 0) {
if (b & 1) { // 如果b的当前位为1
result = (result * a) % m;
}
a = (a * a) % m; // 更新a为a^2
b >>= 1; // b右移一位
}
return result;
}
int main() {
long long a, b, m;
cin >> a >> b >> m;
cout << quick_pow_mod(a, b, m) << endl;
return 0;
}
import java.util.*;
public class Main {
public static long quickPowMod(long a, long b, long m) {
long result = 1;
a %= m; // 先对a取模
while (b > 0) {
if ((b & 1) == 1) { // 如果b的当前位为1
result = (result * a) % m;
}
a = (a * a) % m; // 更新a为a^2
b >>= 1; // b右移一位
}
return result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
long b = sc.nextLong();
long m = sc.nextLong();
System.out.println(quickPowMod(a, b, m));
}
}
def quick_pow_mod(a, b, m):
result = 1
a = a % m # 先对a取模
while b > 0:
if b & 1: # 如果b的当前位为1
result = (result * a) % m
a = (a * a) % m # 更新a为a^2
b >>= 1 # b右移一位
return result
if __name__ == "__main__":
a, b, m = map(int, input().split())
print(quick_pow_mod(a, b, m))
算法及复杂度
- 算法：快速幂取模
- 时间复杂度：
，其中
- 空间复杂度：
