版权信息

​来源​: 自定义题目 ​题目名称​: 取余运算

任务总览表

题目描述

输入 ​b​，​p​，k 的值，求 b^p mod k 的值。其中 ​b​，​p​，k × k 为长整型数。

输入格式

输入 ​b​, ​p​, k 的值。

输出格式

输出 b^p mod k 的值。

样例输入

2 10 9

样例输出

2^10 mod 9=7

提示

• 对于非常大的 ​p​，直接计算 b^p 会导致整数溢出，因此可以利用 模幂算法 来高效计算 ​b^p mod k​。
• 使用 快速幂算法 计算可以大大减少计算复杂度，避免暴力计算时的性能问题。

题目分析

目标

• 给定 ​b​，p 和 ​k​，计算 ​b^p mod k​，即 b^p 对 k 取余的结果。

思路

1. ​直接求解问题​：如果 p 较小，可以直接通过循环计算 ​b^p​，然后再对 k 取余。
2. ​快速幂算法​：如果 p 较大，直接计算 b^p 会超时或导致溢出，使用 快速幂算法 计算会更高效。

快速幂算法

• 快速幂 是一种分治法，可以将指数 p 分解为更小的指数，从而降低计算复杂度。
• 通过递归或迭代的方式实现快速幂，时间复杂度为 ​**O(log p)**​。

时间复杂度分析

• 通过快速幂算法，时间复杂度为 ​**O(log p)**​，其中 p 是指数。因此，即使 p 非常大，算法也能在合理的时间内完成计算。

结论

通过使用快速幂算法，我们能够在 O(log p) 的时间复杂度内高效计算 ​b^p mod k​，解决了大指数下计算的性能问题。