小码匠的信息学江湖:【模板】快速幂

小码匠

发布于 2023-08-31 18:42:52

3010

文章被收录于专栏：小码匠和老码农小码匠和老码农

大家好！我是小码匠。

这是我的编程江湖，这里没有九阴白骨爪，也没有降龙十八掌。

但是，老码农的打狗棒舞的是熠熠生辉，代码敲不好，他就要给我展示打狗棒法了。

本系列是模版系列，会整理

题目链接地址
参考资料
AC代码
自己挖坑（部分题目有）

关于思路大家可参照题目信息的链接地址或者相关书籍，文章旨在分享代码。

题目信息

https://www.luogu.com.cn/problem/P1226
- 题解：https://www.luogu.com.cn/problem/solution/P1226

参考资料

快速幂
- https://oi-wiki.org/math/binary-exponentiation/

自己挖坑

有点抓麻，第一次提交爆零了，泪奔啊，原来=号两边还有空格, 编码习惯好难道也有错吗？

题目描述

给你三个整数 a,b,p，求

a^b

mod p。

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

2 10 9

输出 #1复制

2^10 mod 9=7

说明/提示

样例解释

2^{10}=1024

，1024 mod 9=7。

数据规模与约定

对于 100% 的数据，保证

0≤a,b<2^{31}

，a+b>0，

2≤p<2^{31}

。

AC代码

#include <bits/stdc++.h>

using namespace std;

#define endl '\n';

long long Fast_Power(long long a, long long b, long long mod) {
    long long ans = 1;
    while (b > 0) {
        if (b & 1) {
            ans = ans * a;
            ans %= mod;
        }
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return ans;
}

void best_coder() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long a, b, p;
    cin >> a >> b >> p;
    long long s = Fast_Power(a, b, p);
    cout << a << "^" << b << " mod " << p << "=" << s;
}

void happy_coder() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main() {
    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-08-29，如有侵权请联系 cloudcommunity@tencent.com 删除

编程