题目描述
给出三个整数a,b,m,求a^b mod m的值
输入描述:
一行三个整数a,b,m。
输出描述:
一个整数,表示a^b mod m的值。
实例:
输入: 2 100 1007
输出: 169
思路:
这道题是要先算出a的b次幂再对其结果进行求模(取余),因为b最大可为1e+9,按普通做法来做时间复杂度就太大了,显然这样过不了题,
能快速算a的b次幂,就能减小时间复杂度,快速幂就是一种不错的方法。
什么是快速幂:
快速幂是一种简化运算底数的n次幂的算法,理论上其时间复杂度为 O(log₂N),而一般的朴素算法则需要O(N)的时间复杂度。简单来说快速幂其实就是抽取了指数中的2的n次幂,将其转换为时间复杂度为O(1)的二进制移位运算,所以相应地,时间复杂度降低为O(log₂N)。
代码原理:
以a^13为例,
先把指数13化为二进制就是1101,把二进制数字1101直观地表现为十进制则是如下的等式:
13 = 1 * (2^3) + 1 * (2^2) + 0 * (2^ 1) + 1 * (2^0)
这样一来a^13可以如下算出:
a^13 = a ^ (2^3) * a ^ (2^2) * a ^ (2^0)
完整AC代码如下:
#include <iostream> using namespace std; typedef long long ll;//将long long类型取个别名:ll类型,为了方便 ll ksm(ll a, ll b,ll m) {//ksm:同快速幂 ll ans = 1 % m; while (b) { if ((b & 1) != 0) {//判断b的二进制第一位是否为1,用(b & 1)这个方法还能判断一个数是奇偶数 ans = ans * a % m; } a = a * a % m; b = b >> 1;//去掉二进制的第一位 } return ans; } int main() { ll a, b , m; cin >> a >> b >> m; cout << ksm(a , b , m) << endl; return 0; }