引言
最近在刷题的时候偶然见到这样一个题目，见下图
大致的意思是，让我们计算a的b次方取模p的结果，再我了解了关于快速幂的内容之后，很快便解决了这道题，每次乘完a后取模最后就可以得到结果。但是在这之后，我又碰到了这样一道题，见下图
这个魔性的题目竟然让我求后五百位？这种题用C语言所给的基础内置类型就行不通了 ，可能聪明的你会让人想到高精度，高精＋和-我在之前博客中已经讲过，这道题是要求掌握高精度的乘法才能进一步将此题求解，我在求解完这道题后，便想将之前遗留的坑填上，便写了此篇博客。
快速幂
但是看完题先别急，想让我们看看什么是快速幂。
1.a的平方是a^2，a^2的平方是a^4，以此类推a^8，a^16，a^32。。。
2.a^x * a^y = a^(x+y) 这个也好理解
3.如果我们将b(幂的大小)写成二进制呢？
假设b⑩ = 13 那么b② = 1101
由此我们便可以将a^13，转化成a^8 * a^4 * a^0，而所乘的位数刚好与二进制的一相对应
也就是说，我们可以先自增一个幂次方，每当b出现一位等于1时，向结果乘上一个事先自 增好的幂次方 当遍历完所有b二进制中1的位，便能得到最终的结果。
如果上面的话还没理解，可以结合下面的代码辅助理解，大体的意思就是，不需要一个一个往上乘a，根据幂的二进制直接乘a的更高幂次，减少计算。
while (b > 0) {//代码中用到了&（按位与）和>>（移位符）
if (b & 1) {
//&的作用是比对两个数二进制的每一位，同为1为1，存在0则0
//b = 1 1 0 1
//1 = 0 0 0 1
//result 0 0 0 1
ans = ans * a;//当b&1为真时乘上事先准备的幂次方a，存入结果中
}
a = a * a;
b = b >> 1;
//将二进制位同时向右移动一位，高位补符号位
//b = 1 1 0 1
//b>>1 = 0 1 1 0
//高位补符号位，详情可以去专门看一下我之前的博客或者别人的讲解
//b = b>>1 将结果赋给b
}这样算下来，最终存在ans的结果便是a的b次方了
总的来说，如果 b 在二进制上的某一位是 1，我们就把答案乘上对应的 a^2^n。如果还是不太理解可以看看下面的代码实现，也是第一道题的答案
#include<stdio.h>
int main()
{
long long int a, b, p, ans = 1;
scanf("%lld%lld%lld", &a, &b, &p);
long long int ar = a, br = b;
while (b > 0) {
if (b & 1) {
ans = ans * a % p;//每次注意取模防止数字过大内置类型存不下
}
a = a * a % p;
b = b >> 1;
}
ans = ans % p;
printf("%lld^%lld mod %lld=%lld", ar, br, p, ans);
return 0;
}
看完代码后，是不是就清晰多了？
但我们要考虑一件事，指数的增长速度那么快，用内置类型肯定，放不下，我们用高精度如何？
高精度乘
在了解这种乘法之前，我们可以回忆一下咱们小学的时候是怎样学习乘法运算的。
举个例子——12*19
怎么理解呢？我们可以在这个式子中找找规律，比如右边个位的2和9都是在第0位（由于将数字放入数组中时是从第0位放起），它们相乘也是从第0位开始，19的1和12的2一个是第1位一个是第0位，它们相乘的结果便从第一位开始，而19的1和12的1两个都是第1位，它们在算式计算相加的时候便从第2位也就是百位开始。以上反应的规律总结以下就是
for (int q = 0; q < la; q++) {
for (int p = 0; p < lb; p++) {
sum[q + p] += a[q] * b[p];
}
}
for(int q=0;q<la>lb?la + 3:lb + 3;q++){
sum[q + p + 1] += sum[q + p] / 10;
sum[q + p] %= 10;
}在运用高精乘的过程中，也需要注意关于输入过大放不下的问题，这时候就需要用到字符串的处理，可以看看下方我专门写的一份用于高精乘的代码。
#include <stdio.h>
#include <string.h>
int main()
{
char a0[5008];
char b0[5008];
int a[5008] = { 0 };
int b[5008] = { 0 };
int sum[5008] = { 0 };
int i = 0;
scanf("%s", a0);
scanf("%s", b0);
int v = 0;
for (v = 5001; a0[v] != '\0'; v--);
v--;
for (int c = 0; v >= 0; c++, v--) {
a[c] = a0[v] - '0';
}
for (v = 5002; b0[v] != '\0'; v--);
v--;
for (int c = 0; v >= 0; c++, v--) {
b[c] = b0[v] - '0';
}
//以上代码将字符串转为数字放入数组
int la = strlen(a0);
int lb = strlen(b0);
int lc = la + lb;
for (int q = 0; q < la; q++) {
for (int p = 0; p < lb; p++) {
sum[q + p] += a[q] * b[p];
}
}
for(int q=0;q<la>lb?la + 3:lb + 3;q++){
sum[q + p + 1] += sum[q + p] / 10;
sum[q + p] %= 10;
}
//以上代码进行高精乘
int j = 0;
for (j = 5005; sum[j] == 0; j--);
for (; j >= 0; j--)
printf("%d", sum[j]);
//以上代码打印结果
return 0;
}当快速幂遇见高精乘
这时候再将开始那道题搬运下来看看
这道题说白了最后要求求后500位其实是之前两者知识点的结合体，不过先讲讲第一问，问你位数，由于2^P-1的结果与2^P是相同的，所以可以列方程
m刚刚好就是最终位数，在math.h中有计算lg的函数我们直接调用即可。
最终代码放到下面，配上注释
#include<stdio.h>
#include<math.h>
int arr[505];//充当计算2的幂次方的一个过程
int sign[505];//存放2的幂次方
int res[505];//充当最终结果的一个过程
int now[505];//存放最终结果
int main()
{
int P;
int ws; int i, j;
scanf("%d", &P);
ws = P * log10(2) + 1;
sign[0] = 2;
res[0] = 0;
now[0] = 1;
while (P > 0) {
if (P & 1) {//当P&1为真，结果乘上2的幂次方
for (i = 0; i <= 500; i++) {
for (j = 0; j <= 500; j++) {
if (i + j <= 500)//防止计算越界
res[i + j] += now[i] * sign[j];
}
}
for (i = 0; i <= 500; i++) {
if (res[i] > 9) {
res[i + 1] += res[i] / 10;
res[i] %= 10;
}
}
for (i = 0; i <= 500; i++) {
now[i] = res[i];
res[i] = 0;//用完res后要清零
}
}
//下面是2的幂次方的自乘和自增
for (i = 0; i <= 500; i++) {
for (j = 0; j <= 500; j++) {
if (i + j <= 500)//防止计算越界
arr[i + j] += sign[i] * sign[j];
}
}
for (i = 0; i <= 500; i++) {
if (arr[i] > 9) {
arr[i + 1] += arr[i] / 10;
arr[i] %= 10;
}
}
for (i = 0; i <= 500; i++) {
sign[i] = arr[i];
arr[i] = 0;//用完arr计算2的幂次方后清零
}
P >>= 1;//二进制P右移一位
}
now[0]--;//最终结果减一
printf("%d\n", ws);
for (i = 499,j=0; i >= 0; i--) {//华丽打印结果
printf("%d", now[i]);
j++;
if (j >= 50) {
printf("\n");
j = 0;
}
}
return 0;
}结语
以上便是本次快速幂以及高精度乘法的所有内容，如果感觉对你有帮助的话，还请点个小小的赞，留下关注收藏再走啊！比心-----♥
