题解：P1226 【模板】快速幂

· · 题解

题解

P1226 【模板】快速幂

题目传送门

"luogu.me"阅读

题目描述

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

输入格式

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

输出格式

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

解题思路

快速幂简介

快速幂算法是一种高效计算幂运算的方法，尤其适用于大指数的幂运算。其核心思想是通过将指数 b 进行二进制分解，从而将幂运算转化为多个平方运算的乘积，从而大大减少计算量。

快速幂算法的步骤：

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

AC Code:

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

#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;
}

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