题解

P1226 【模板】快速幂

题目描述

给定三个整数 $a, b, p$ ，要求计算 $a^b \bmod p$ 。

输入格式

输入只有一行三个整数，分别代表 $a, b, p$ 。

输出格式

输出一行一个字符串 a^b mod p=s，其中 $a, b, p$ 分别为题目给定的值， $s$ 为运算结果。

解题思路

快速幂简介

快速幂算法是一种高效计算幂运算的方法，尤其适用于大指数的幂运算。其核心思想是通过将指数

b

进行二进制分解，从而将幂运算转化为多个平方运算的乘积，从而大大减少计算量。

快速幂算法的步骤：

初始化结果为 $1$ 。
当 $b > 0$ $b > 0$ 时，进行以下操作：
- 如果 $b$ 是奇数，将结果乘以 $a$ 并取模 $p$ 。
- 将 $a$ 平方并取模 $p$ 。
- 将 $b$ 右移一位（即除以 $2$ ）。之所以不用 b/=2 ,是因为右移的用时更少 $($ 理论上来说,但是实测 b/=2 也可以 $)$ 。
最终结果即为 $a^b \bmod p$ 。

AC Code:

AC Code编译模式： C++14(GCC9)

CPP

#include<bits/stdc++.h>
using namespace std;
long long fastPow(long long a, long long b, long long p) {
//十年OI一场空，不开 long long 见祖宗
    long long result = 1;
    while (b > 0) {
        if (b & 1) {  // 如果b是奇数
            result = result * a % p;
        }
        a = a * a % p;  // a的平方
        b >>= 1;  // b右移一位
        //将 "b >>= 1" 改为 "b /= 2" 也可以！
    }
    return result;
}

int main() {
    long long a, b, p;
    cin >> a >> b >> p;
    long long s = fastPow(a, b, p);
    cout << a << "^" << b << " mod " << p << "=" << s << endl;
    return 0;
}

蒟蒻的第一个 【模板】 题目题解，求过

题解：P1226 【模板】快速幂

文章操作

题解

P1226 【模板】快速幂

题目描述

输入格式

输出格式

解题思路

快速幂简介

快速幂算法的步骤：

AC Code:

相关推荐

评论

题解：P1226 【模板】快速幂