题目链接

题目描述

给你三个整数 $b,p,k$，求 $b^p \bmod k$。

输入格式

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

输出格式

输出一行一个字符串 b^p mod k=s，其中 $b, p, k$($0 \le b,p < 2^{31},1 \le k \le 2^{31}$) 分别为题目给定的值，$s$ 为运算结果。

题解

如此巨大的数据，当然不能直接暴力，考虑幂次方的性质，要求 $a^4$ 相当于求出 ${a^2}^2$，以此类推，对 $b$ 作二进制分解，只用求出二进制位上为 $1$ 的位之积就是答案

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll b, p, k;
ll fast_pow(ll b, ll p, ll k) {
    ll res = 1 % k;
    while (p) {
        if (p & 1)
            res = res * b % k;
        b = b * b % k;
        p >>= 1;
    }
    return res;
}
int main() {
    scanf("%lld%lld%lld", &b, &p, &k);
    printf("%lld^%lld mod %lld=%lld", b, p, k, fast_pow(b, p, k));
    return 0;
}

注意

1. 数据经过更新，要考虑 $k = 1$ 的情况所以 res = 1 % k