一、快速幂的介绍:
1、为什么要使用快速幂:
当我们计算a的n次幂时,最先想到的肯定是c中的内置函数 pow(a,n),这个内置函数虽然简单方便,但是在实际使用中这个函数的时间复杂度是o(n),因为它是将a乘n次得到的答案。
由于在n非常大时用pow()很容易超时,因此我们引入一个时间复杂度为o(log n)的算法——快速幂
2、快速幂的原理:
快速幂的实现原理其实非常简单,我们可以把a的n次幂中的那个n当做一个二进制数,例如10我们把他看做 1010,我们在快速幂的算法中只考虑有1的位置,因此a的10次幂就化为,a的八次幂×a的2次幂。 (直接这样看看可能会一头雾水,可以配着下面的代码理解)
3、快速幂的代码
long long fast_power(a,n){
int res=1;// res为1可认为现在res为0次幂
while(n){
if(n&1==1){res=res*a;}
n=n>>1;// n向右移一个二进制位 搜寻下一个为1的位置
a=a*a; // a以这种方式 从a的一次方 变为a平方 再变为a的四次方...... 刚好与为1的位置对应
}
return res;
}
二、快速幂的进阶(答案要取mod):
话不多说直接上 例题和ac代码:https://ac.nowcoder.com/acm/problem/15187
#include<bits/stdc++.h>
using namespace std;
long long mod;
long long fast(long long x,long long n){
x=x%mod;
long long ans=1;
while(n){
if(n&1==1){ans=ans*x%mod;}
x=x*x%mod;
n>>=1;
}
return ans%mod;
}
int main(){
long long a,b,c,d;
cin>>a>>b>>c>>d>>mod;
cout<<fast(a,c*d)*fast(b,c*d)%mod<<endl;
}
标签:res,long,x%,----,算法,ans,数据结构,快速,mod
From: https://blog.csdn.net/2301_77961281/article/details/136634900