欢迎您访问 最编程 本站为您分享编程语言代码，编程技术文章！

热门搜索/Hot Search

您现在的位置是： 首页

快速幂算法--求 a^b % p 的快速方法

最编程 2024-03-09 09:03:14
...

先想暴力怎么求解

可以循环b次，每次从而求出a^b % p，时间复杂度为O(b)，而这里的b是很大的，达到了2 * 10 ^ 9数量级，所以这么做会TLE

 1 #include <iostream>
 2 using namespace std;
 3 int main() {
 4     int a, b, p;
 5     long long res = 1;
 6     cin >> a >> b >> p;
 7     while(b--)
 8         res = res * a % p;
 9     cout << res << endl;
10 }

如何优化？

我们可以用二分的思想来优化：

1) 如果b是偶数，我们可以将b / 2，求出a ^ (b / 2)，然后再求平方；

2) 如果b是奇数，我们可以先将b - 1，b - 1即为偶数，记b' = b - 1，求出a ^ (b' / 2)，求平方后再乘以a，仍然可以得到正确结果

3) 递归出口为a ^ 0 = 1

以上就是递归求快速幂的思路，代码如下：

 1 //递归快速幂
 2 int qmi(int a, int n)
 3 {
 4     if (n == 0)
 5         return 1;
 6     else if (n % 2 == 1)
 7         return qmi(a, n - 1) * a;
 8     else
 9     {
10         int temp = qmi(a, n / 2);
11         return temp * temp;
12     }
13 }

 

这里的temp是需要的，如果不加temp的话，直接return qmi(a, n / 2) * qmi(a, n / 2)，那么会计算两次an/2，这样算法就退化成了O(n)。

在实际问题中，题目常常会要求对一个大素数取模，这是因为计算结果可能会非常巨大，但是在这里考察高精度又没有必要。这时我们的快速幂也应当进行取模，此时应当注意，原则是步步取模，如果MOD较大，还应当开long long。

 1 //递归快速幂（对大素数取模）
 2 #define MOD 1000000007
 3 typedef long long ll;
 4 ll qpow(ll a, ll n)
 5 {
 6     if (n == 0)
 7         return 1;
 8     else if (n % 2 == 1)
 9         return qpow(a, n - 1) * a % MOD;
10     else
11     {
12         ll temp = qpow(a, n / 2) % MOD;
13         return temp * temp % MOD;
14     }
15 }

 递归虽然简洁，但会产生额外的空间开销。我们可以把递归改写为循环，来避免对栈空间的大量占用，也就是非递归快速幂。

非递归快速幂

这里用一个例子更形象地说明，比如计算7的10次方；这里可以把10写成二进制，即(1010)2

也就是计算 7(1010)2 可以把它拆成 7(1000)2 * 7(10)2

对于任意的整数，我们都可以把它拆成二进制数的形式

那么，我们就可以每次将底数平方，从而不断地得到我们所需要的乘数因子

上代码：

 1 //非递归快速幂
 2 int qpow(int a, int n){
 3     int ans = 1;
 4     while(n){
 5         if(n&1)        //如果n的当前末位为1
 6             ans *= a;  //ans乘上当前的a
 7         a *= a;        //a自乘
 8         n >>= 1;       //n往右移一位
 9     }
10     return ans;
11 }

 

仔细推敲代码过程：

最初ans为1，然后一位一位算：

1010的最后一位是0，所以a^1这一位不要。然后1010变为101，a变为a^2。（a ^ 2）

101的最后一位是1，所以a^2这一位是需要的，乘入ans。101变为10，a再自乘。(a ^ 4)

10的最后一位是0，跳过，右移，自乘。(a ^ 8)

然后1的最后一位是1，ans再乘上a^8。循环结束，返回结果。

>>是右移，表示把二进制数往右移一位，相当于/2；&是按位与，&1可以理解为取出二进制数的最后一位，相当于%2==1。

下面给出Acwing上模板题的代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define int long long 
 4 
 5 int qmi(int a, int b, int p) {
 6     int ans = 1;
 7     while(b) {
 8         if(b & 1) ans = ans * a % p;
 9         a = a * a % p;
10         b = b >> 1;
11     }
12     return ans;
13 }
14 
15 signed main() {
16     int T;
17     cin >> T;
18     while(T--) {
19         int a, b, p;
20         cin >> a >> b >> p;
21         int res = qmi(a, b, p);
22         cout << res << '\n';
23     }
24     return 0;
25 }

 

 

 

参考博客

https://zhuanlan.zhihu.com/p/95902286

上一篇： 求 a 和 b 的最大公约数

下一篇： 关于个人做淘宝客网站

推荐阅读