a^b%p
程序员文章站
2022-04-01 17:21:06
...
a^b
求 a 的 b 次方对 p 取模的值。
输入格式
三个整数 a,b,p ,在同一行用空格隔开。
输出格式
输出一个整数,表示a^b mod p的值。
数据范围
1≤a,b,p≤1e9
输入样例:
3 2 7
输出样例:
2
时/空限制: 1s / 32MB
这道题刚看会发现诶,直接循环就完了嘛,但是一看下面的数据范围就会发现,如果直接循环,一定会超时。
那怎么做呢?
这里就是一个典型快速幂的题目,我们可以吧a^b分解,利用二进制的特性,从低位乘到高位,如果那一位是0就代表不需要乘,1则反之。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b,p;
cin>>a>>b>>p;
int res=1%p;//防止p是0的情况出现
while(b)
{
if(b&1) res*=1ll*a%p;//1ll是把res和a强转为long long
a*=1ll*a%p;
b>>=1;//b右移
}
cout<<res<<endl;
return 0;
}
上一篇: 虚线圆
推荐阅读
-
平价之选 影驰B360M M.2主板详细分析评测
-
怎么判断原装粉与劣质粉? 富士施乐m158b打印机墨粉粉的选购方法
-
华为Mate30EPro和华为p40区别是什么 华为Mate30EPro和华为p40对比介绍
-
PTC CREO 4.0 B000在线安装详细教程(附下载)
-
华为p50 pocket和iPhone13哪个好 华为p50 pocket和iPhone13对比评测
-
加法变乘法——第六届蓝桥杯C语言B组(省赛)第六题
-
Matlab R2019b Mac版安装许可激活图文教程(含许可文件+密钥)
-
b站账号被封怎么办 哔哩哔哩账号封禁原因查询方法
-
ORA-01403:no data found 及 select a into b 空值
-
华硕P5GPL-X SE开机保护维复一例