快速幂算法
主要用途:快速求出(a^k)%p的结果—>O(logk)
主要思路:快速幂的思想就是反复平方法,预先处理出来需计算的值。
手动模拟一下会发现,是将10进制的数转换为了2进制,主要是将指数k化为2进制。
举个🌰
需要求($4^5$)%10,5的二进制就是101
也就是($ 4 ^{101} $)%10–此处的101为二进制
可以拆成($4^{2^0}$)*($4^{2^2}$)
计算可得
$4^{2^0}$ %10=4
$4^{2^1}$ %10=6
$4^{2^2}$ %10=6
所以$4^5$%10 = (4*6) % 10 = 24
算法1
精妙之处就在k&1,这样就直接利用的二进制进行判定,也就是只计算二进制幂次和。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//a^k mod p
int qmi(int a,int k,int p)
{
int res=1;
while(k)//本质是求k的二进制表示
{
//k&1指的k的个位
if(k&1) res = (LL)res*a%p;
k>>=1;//删掉k的末尾位
a=(LL)a*a%p;//平方一下变成下一个
}
return res;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int a,k,p;
scanf("%d%d%d",&a,&k,&p);
printf("%d\n",qmi(a,k,p));
}
return 0;
}