AcWing 89. $\Huge\color{red}{a^b(三种思路!!!)}$
原题链接
简单
作者:
种花家的老六
,
2022-11-21 22:53:21
,
所有人可见
,
阅读 395
<- 求赞
思路1(暴力)
暴力枚举b,不停的乘a,最后%p。
时间复杂度:$O(b)$
肯定会超时,还会超内存。
思路2(暴力优化)
不在最后%p,是边乘边模p。
还是会超时,但内存不会超了。
思路3(快速幂)
这也是我们的最终写法。
举个例子:
比如说我们要求3的1000000次方是多少。
可以先算3^1,3^2………………3^(2^19)是多少。
再算1000000的二进制是多少,如果这一位是1,那么就把这一位对应的3的多少次方乘起来。
时间复杂度:$O(log _ 2n)$
c++代码(此处只展示快速幂解法):
#include <iostream>
using namespace std;
int main()
{
int a, b, p;
cin >> a >> b >> p;
int res = 1 % p;
while (b)
{
if (b & 1) res = (long long)res * a % p;
a = (long long)a * a % p;
b >>= 1;
}
cout << res << endl;
return 0;
}
谢谢大佬