P1226 【模板】快速幂||取余运算

题目链接

题目描述

给你三个整数 $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$ 的位之积就是答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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
文章作者: answerend42
文章链接: http://answerend42.github.io/2020/11/21/lg1226/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 answerend42的Blog