算法 —— 快速幂
目录
P1045 [NOIP2003 普及组] 麦森数
P1226 【模板】快速幂
原理I
原理II
P1226 代码解析
P1045 代码解析
P1045 [NOIP2003 普及组] 麦森数
本题来自洛谷：P1045 [NOIP2003 普及组] 麦森数，根据题意，我们可以看到本题需要计算最少2的1000次方，如果我们要从2的1次方开始计算需要乘二1000次，这无疑是需要消耗大量时间的，在解决本题之前可以先学习一下下面算法：快速幂
P1226 【模板】快速幂
本题来自洛谷：P1226 【模板】快速幂，题目已经告诉你需要使用快速幂算法来解决问题。
根据题解大佬给出的介绍，本蒟蒻对此进行了总结：
很显然，快速幂算法就是为了解决大量乘法次数而产生的，这种算法可以让计算机快速计算出
a^b，暴力相乘的话，电脑要计算 b 次，用快速幂，计算次数在 log(b) 级别。
原理I
先看以下幂运算的特性，相信大家觉得不难：
了解了这些特性，我们可以利用它来解决问题，过程如下：
- 幂与1进行按位与运算
- 为1就说明该位对应的二进制存在，需要乘
- 为0说明该位对应的二进制不存在，a自乘提升后的值不需要乘
直接来一个例子给大家更好的认识此过程：
假设我们拿到了 𝑎，并且 𝑏=11。想求 𝑎 ^ 11，但是又不想乘11次，有点慢。以电脑视角稍稍观察一下 𝑏=11，二进制下是 𝑏=1011。
制作一个 𝑏𝑎𝑠𝑒。现在 𝑏𝑎𝑠𝑒=𝑎，表示的是，𝑎 ^ 1 = 𝑎，待会 𝑏𝑎𝑠𝑒会发生改变的。
制作一个 𝑎𝑛𝑠，初值 1，准备用来做答案。
由于11的二进制有4位，所以我们要进行4次循环判断：
1、循环一，看 𝑏 的最后一位是 1 吗？ 如果是，代表 a 的一次方存在，以 𝑎𝑛𝑠 ∗= 𝑏𝑎𝑠𝑒。
if(b & 1)ans *= base;/*关于 b & 1：
x & y 是二进制 x 和 y 的每一位分别进行“与运算”的结果。
与运算，即两者都为 1 时才会返回 1，否则返回 0。
那么 b & 1二进制
b = 1011
1 = 0001
b&1 = 0001因为 1（二进制）的前面几位全部都是 0，
所以只有 b 二进制最后一位是 1 时，b & 1 才会返回 1。*/判断完成之后base上升一次（自乘）
base *= base;同时b最低位就要舍弃掉了，下一次循环用前一位来与1进行按位与运算，舍弃方式直接右移一位。
b >>= 1;2、循环二，再看看 𝑏，此时b的二进制表示为101，最后一位还是 1，这说明有 a 的二次方存在，我们依旧𝑎𝑛𝑠 ∗= 𝑏𝑎𝑠𝑒（此时base为a的二次方），继续进行上述操作。
3、循环三，继续看看 𝑏，此时b的二进制表示为10，最后一位是0，说明 a 的三次方不存在了，我们不需要让ans *= base，但是base还要继续自乘上升，因为 b 还没变成0，判断条件依旧成立。
4、循环四， 𝑏 此时为1了，按位与后成立，说明有 a 的四次方，依旧𝑎𝑛𝑠 ∗= 𝑏𝑎𝑠𝑒（base此时为a的四次方）b右移一位后变成0，循环结束。
总的来说，如果 𝑏 在二进制上的某一位是 1，我们就把答案乘上对应的 a^(2^n)。代码如下：
int quickPower(int a, int b)//求a的b次方
{int ans = 1, base = a;//ans为答案，base为a^(2^n)while(b > 0)//b是一个变化的二进制数 每次循环右移位变零{//b&1表示b在二进制下最后一位是不是1，如果是：把ans乘上对应的a^(2^n)if(b & 1)ans *= base;base *= base;//base自乘，由a^(2^n)变成a^(2^(n+1))b >>= 1;//位运算，b右移一位}return ans;
}可以看到上述代码只需要循环4次就可以求出2的11次方，而用一个变量不断乘2需要11次循环才能实现，这无疑是大大提高了效率。
原理II
快速幂有很多种理解方式。从头开始，看以下图片
可以看到我们凭借幂是否为奇数将3的11次方拆成了好几个小部分，依次运算，那么用代码如何实现呢？先看思路：假设我们以3的11次方为例
第一层循环，𝑏=11，一个奇数。将 3 ^ 11 分解来看，本层只需把 𝑎𝑛𝑠 ∗= 3。那后面的3 ^ 10呢？我们到下一层再搞定。下几层的总目标是让 𝑎𝑛𝑠∗= 3 ^ 10，也就是让 𝑎𝑛𝑠∗=9 ^ 5。来到下一层的是 𝑥 = 3 ∗ 3 = 9 且 𝑏 = 11 / 2 = 5。
第二层循环，几乎独立于第一层存在。𝑏=5，一个奇数。将 9 ^ 5 分解为 9 * 9 ^ 4 来看。本层只需把 𝑎𝑛𝑠∗=9，后面的我们到下一层再搞定。下几层的总目标是让 𝑎𝑛𝑠∗= 9 ^ 4，也就是让 𝑎𝑛𝑠∗=81 ^ 2。于是 𝑥 = 9∗9 = 81 且 𝑏 = 5/2 = 2。
第三层循环，𝑏=2，不是奇数，只把 81 ^ 2 当作 (81 ^ 2) ^ 1。下几层的总目标是让 𝑎𝑛𝑠∗=81^2。于是 𝑥=81∗81=6561，𝑏=2/2=1。
第四层循环，𝑏=1，是奇数。这时候已经不用看成什么分解了，𝑎𝑛𝑠∗=6561 就可完成总目标，b/2 为 0，结束循环。
代码和上面一样，因为 𝑏 & 1 与 𝑏 % 2 == 1 等效。𝑏 /= 2 与 𝑏 >>= 1 等效。
很显然上述思路是一个分治思想，下面附上代码：
int quick_pow(int a, int b) // a为底数 b为幂
{if (b == 1) //最后一层 没办法再分return a;else{int c = quick_pow(a, b / 2);if (b % 2 == 0) // 81^2这种情况return c * c;elsereturn c * c * a; // 3 * ((3^2)^5)}
}P1226 代码解析
快速幂经常要结合取余运算，这里介绍取余运算有一些好用的性质，包括：
- ( A + B ) % b = ( A % b + B % b ) % b
- ( A × B ) % b = ( ( 𝐴 % 𝑏 ) × ( 𝐵 % 𝑏 ) ) % 𝑏
学习完以上内容，我们尝试解决最开始留下的问题吧，首先是【模板】快速幂的代码解析：
利用上述性质可以解决本题，不要缩短运算时间后就认为问题解决了，试想一下当数据超过了long long的最大值应该如何解决，所以我们在运算时就要着手处理取余操作。
#include<bits/stdc++.h>
using namespace std;
//注意本题 a 和 b 都可能为INT_MAX 用int不够
long long quickPower(long long a, long long b, long long c)
{long long ans = 1, base = a;while (b > 0){if (b & 1){ans *= base;ans %= c; }base *= base;base %= c;b >>= 1;}return ans;
}int main()
{long long a, b, p; cin >> a >> b >> p;cout << a << '^' << b << " mod " << p << '=' << quickPower(a, b, p) << endl;return 0;
}
P1045 代码解析
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int f[1001],p,res[1001],sav[1001];//乘法要开两倍长度
void result_1()
{memset(sav,0,sizeof(sav));for(register int i=1;i<=500;i+=1)for(register int j=1;j<=500;j+=1)sav[i+j-1]+=res[i]*f[j];//先计算每一位上的值（不进位）for(register int i=1;i<=500;i+=1){sav[i+1]+=sav[i]/10;//单独处理进位问题，不容易出错sav[i]%=10;}memcpy(res,sav,sizeof(res));//cstring库里的赋值函数，把sav的值赋给res
}
void result_2()//只是在result_1的基础上进行了细微的修改
{memset(sav,0,sizeof(sav));for(register int i=1;i<=500;i+=1)for(register int j=1;j<=500;j+=1)sav[i+j-1]+=f[i]*f[j];for(register int i=1;i<=500;i+=1){sav[i+1]+=sav[i]/10;sav[i]%=10;}memcpy(f,sav,sizeof(f));
}
int main()
{scanf("%d",&p);printf("%d\n",(int)(log10(2)*p+1));res[1]=1;f[1]=2;//高精度赋初值while(p!=0)//快速幂模板{if(p%2==1)result_1();p/=2;result_2();}res[1]-=1;for(register int i=500;i>=1;i-=1)//注意输出格式，50个换一行，第一个不用if(i!=500&&i%50==0)printf("\n%d",res[i]);else printf("%d",res[i]);return 0;
}