问题 H: 取余运算

2024-01-07 21:47:18

题目描述

输入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);
}

文章来源:https://blog.csdn.net/lcc1737/article/details/135429584
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。