[洛谷 1226,codevs 3500]快速幂

题目链接

https://www.luogu.org/problem/P1226

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

题解

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

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

快速幂采用了倍增的方法，在计算 \(2^4\) 时，不是传统地计算 \(2 \times 2 \times 2 \times 2\)，而是计算 \(2^2 \times 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;
}