分治法 —— 取余运算 (快速幂)

取余运算

题目描述

给你三个整数 b,p,k，求 b^p mod k

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

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

输入
2 10 9
输出
2^10 mod 9=7
说明/提示
2^10 = 10242 1024 mod 9=7
数据规模与约定
对于 100%100% 的数据，保证 0 <= b,p < 2^31, 1 < k < 2 ^31

题目链接

取余运算 (快速幂)

题解

如果有小伙伴不知何为快速幂，或者说快速幂的递归和迭代方式如何编写。可以参考博客分治法 —— 快速幂

知道快速幂后该题可以轻轻松松的拿下啦！

b, p 的取值范围：0 <= b,p < 2^31 ，不可能说将b ^ p 的数先计算出来再求余的，非常不现实。

还有一个知识点需要注意，即同余原理。何为同余原理?我们不是搞数学的，无需知道定理如何来的， 我们知道如何使用即可!

即 （a * b * c *…） % k

=( (a %k) * (b %k) * (c%k) … ) % k

在递归求快速幂的过程中不断的对k求余即可，代码如下

Code

#include <iostream>
#include <cstdio>
using namespace std;
long long k;
//取余运算的性质
//同余  (a * b) % k = ( (a % k) * (b * k) ) % k;
//(a * b * c) % k =  ((a % k) * (b % k) * (c % k))
long long fun(long long b, long long p)
{long long t;if (p == 0)//递归边界return 1;t = fun(b, p / 2) % k;//此语句无论是在if和else中都会执行，故直接放到f else 外面来if (p % 2 == 1){return t * t * b % k;}else {return t * t % k;}
}
int main()
{long long b, p;cin >> b >> p >> k;cout << b << "^" << p << " mod " << k << "=" << (fun(b, p) % k)<< endl;return 0;
}

当然实在不懂同余运算为什么可以这样算，所有的数据都可以这样算嘛?为什么这样写可以是正确的。如何验证正确性呢?

我们不是研究数学的，有兴趣的可以自行百度，此处也推荐视频链接https://www.bilibili.com/video/BV12a4y1v7EF