问题 H: 取余运算

题目描述

输入b，p，k的值，求b^p mod k的值（即b的p次方除以k的余数）。其中b，p，k*k为32位整数。

输入

输入b，p，k的值

输出

输出b^p mod k的值

样例输入

2 10 9

样例输出

2^10 mod 9=7

方法一：

分治策略求解：

问题分析

1. 递归方法:

   • 使用递归函数 ans 来分解幂运算，这是一种分治策略。
   • 递归方法允许将问题分解为更小的子问题，这些子问题更容易解决。

2. 处理基本情况:

   • 当 p 等于 1 或 2 时，有特定的返回条件，这些是递归的基本情况。

3. 偶数和奇数幂:

   • 当 p 是偶数时，b^p 可以分解为 (b^(p/2))^2。
   • 当 p 是奇数时，b^p 可以分解为 (b^(p/2))^2 * b。

4. 模运算的性质:

   • 利用模运算的性质 (a * b) mod k = ((a mod k) * (b mod k)) mod k 来避免中间结果过大。

5. 递归的终止条件:

   • 递归将持续进行，直到 p 降至 1 或 2，这时可以直接计算并返回结果。

#include <bits/stdc++.h>
#define int long long // 使用长整型以支持大数运算
using namespace std;

// 定义一个函数 ans 来计算 b^p mod k
int ans(int b, int p, int k) {
    // 如果幂 p 等于 1，直接返回 b mod k
    if (p == 1) {
        return b % k;
    }
    // 如果幂 p 等于 2，返回 b^2 mod k
    if (p == 2) {
        return b * b % k;
    }
    // 如果幂 p 是偶数
    if (p % 2 == 0) {
        // 递归计算 b^(p/2) mod k
        int m = ans(b, p / 2, k);
        // 使用模运算的性质：(a * a) mod k = (a mod k * a mod k) mod k
        return m * m % k;
    } else {
        // 如果幂 p 是奇数
        // 先递归计算 b^(p/2) mod k
        int m = ans(b, p / 2, k);
        // 然后再乘以 b，并进行模运算
        return m * m % k * b % k;
    }
}

signed main() {
    int b, p, k;
    cin >> b >> p >> k;
    printf("%lld^%lld mod %lld=%lld", b, p, k, ans(b, p, k));
}

方法二：

快速幂

问题分析

快速幂算法:

使用快速幂算法来高效地分解幂运算。
快速幂算法通过二进制展开指数 p 来减少计算量。

二进制分解:

指数 p 被分解为二进制形式，算法通过迭代每个二进制位来累计结果。

迭代和模运算:

在每次迭代中，如果当前的指数位为 1，将相应的 b 的幂乘入结果。
b 每迭代一次，进行平方并取模，以保持结果在可管理的大小。

#include <bits/stdc++.h>
#define int long long // 使用长整型以支持大数运算
using namespace std;

signed main() {
    int b, p, k;
    cin >> b >> p >> k; // 读取基数 b，指数 p 和模数 k
    int res = 1; // 初始化结果为 1
    int by = b, py = p; // 保存原始的 b 和 p 值，用于最后的输出
    // 快速幂算法
    while (p) {
        // 如果 p 的当前最低位是 1，则将当前的 b 乘入结果
        if (p & 1) res = res * b % k;
        p >>= 1; // 将 p 右移一位，等同于 p 除以 2
        b = b * b % k; // 将 b 平方后取模
    }
    // 输出结果
    printf("%lld^%lld mod %lld=%lld", by, py, k, res);
}