AcWing P89:a^b(快速幂)

发布时间:2024年01月22日

问题描述

求 a 的 b 次方对 p 取模的值。

输入格式

三个整数 a, b, c 在同一行用空格隔开。

输出格式

输出一个整数,表示 a^b mod p 的值。

数据范围

0\leq a,b\leq 10^{9}
1\leq p\leq 10^{9}

输入样例

3 2 7

输出样例

2

解题思路

解法:位运算,快速幂。

根据数学知识,每个正整数可以唯一表示为若干个指数不重复的 2 的次幂的和。对于给定的次方数 b 如果在二进制表示下有 k 位,第 i(0 ≤ i < k)位的数字是 ci(0 或 1),可得:

b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+\cdots+c_02^{0}

代入 a 的 b 次方表达式,可得:

a^{b}=a^{c_{k-1}*2^{k-1}}*a^{c_{k-2}*2^{k-2}}*\cdots*a^{c_0*2^{0}}

对于每一个乘积项,可得:

a^{2^{i}}=a^{2^{i-1}*2}=(a^{2^{i-1}})^{2}

b 的二进制表示位数即 k 的值为:

k=\left \lceil log_{2}(b+1) \right \rceil

所以可以遍历 b 在二进制表示下的所有数位:通过 b>>1 的移位运算进行 k 次递推,求出每个乘积项;通过 b&1 运算得出最低位的 ci 值;当 ci = 1?时,把乘积项累积到答案中。

算法的时间复杂度是O(log_{2}b)

参考代码

#include<bits/stdc++.h>
using namespace std;
int power(int a,int b,int p){
	int ans=1%p;
	for(;b!=0;b>>=1){
		if(b&1==1) ans=(long long)ans*a%p;
		a=(long long)a*a%p;
	}
	return ans;
}
int main(){
	int a,b,p,ans;
	cin>>a>>b>>p;
	ans=power(a,b,p);
	cout<<ans;
} 

文章来源:https://blog.csdn.net/m0_73514832/article/details/135721338
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。