引言

最近在刷题的时候偶然见到这样一个题目，见下图

 大致的意思是，让我们计算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 1ans = 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;
}

结语

以上便是本次快速幂以及高精度乘法的所有内容，如果感觉对你有帮助的话，还请点个小小的赞，留下关注收藏再走啊！比心-----♥