[洛谷 1226,codevs 3500]快速幂

题目链接

https://www.luogu.org/problemnew/show/P1226

http://codevs.cn/problem/3500/

题解

对于传统的求幂运算,时间复杂度达到了\(O(n)\),在数据量过大的时候毫无悬念会TLE,有没有一种计算更快的方法呢?

于是,快速幂就应运而生了。

快速幂采用了倍增的方法,在计算2^4时,不是传统地计算\(2*2*2*2\),而是计算\(2^2*2^2\),将时间复杂度优化到了\(O( \log n)\),确保在long long的数据范围内都能够迅速出解。

#include <iostream>
using namespace std;
long long a,b,c;
long long qpow(long long a,long long b,long long c)
{
 long long ans=1;
 while(b>0)
 {
  if(b%2)ans=((ans%c)*(a%c))%c;
  a=a*a%c;
  b>>=1;
 }
 return ans%c;
}
int main()
{
 cin>>a>>b>>c;
 cout<<a<<'^'<<b<<" mod "<<c<<'='<<qpow(a,b,c);
 return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注