Processing math: 20%

[洛谷 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 的数据范围内都能够迅速出解。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理