引言
最近在刷题的时候偶然见到这样一个题目，见下图
大致的意思是，让我们计算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; }
结语
以上便是本次快速幂以及高精度乘法的所有内容，如果感觉对你有帮助的话，还请点个小小的赞，留下关注收藏再走啊！比心-----♥
