【Week 2题解】快速幂取余

· · 算法·理论

题目链接：【模板】快速幂取余

截至23/05/11，本题的完成情况:

        可见数据并不十分理想。作为第二道作业题，本题所设置的样例数据同样略显BT复杂，是为了让同学们认识到算法优化的重要性。

Part 1 暴力枚举运算

        首先我们来看到题目的要求：

给你三个整数 a,b,p，求 a^b\ \% \ p 的值。

        很好，我们发现了最为基础的核心计算法则，即：

先求a^b的值，并将这个结果对p取模。

        因此我们可以很轻易地写出以下代码：

ans=1
for i in range(0,b):
    ans * = a
ans % = p
print(ans)

在C语言中则体现为

int ans = 1;
for(int i=0;i<b;i++)
    ans * = a;
ans % =p;
printf("%d",ans);

        很好，这说明你已经了解了这题最为基础的结构，那么让我们来看看得分的情况吧！

情况貌似并不尽人意，是哪里出问题了呢？

Part 2 “一步一模”的谨慎前行

        通过对比一些较大数据的输入与输出反馈，我们可以发现，很多结果似乎变成了不可能出现的负数

这时我们再度回到题目要求，会发现：

将 a^b 的最终结果对 p 取模，本质上是以 |p| 作为溢出边界进行运算。

        那么应该如何控制运算过程中的数据一直在要求的范围内呢？

        答案也很简单：

对于每一步 a*b 的运算，都将其结果对 p 进行取模。

        代码与前文所述大同小异，但多少还是进行了一些优化。因此让我们再来看看初步优化过后的运行结果吧！

        嗯，貌似要好了不少。只可惜当程序运算到更大的数值时，对于数据的处理貌似过于复杂从而导致超时了

Part 3 “数据拆解”的进制转换

        那么在处理天文数字的数据时，应该如何将我们的算法进一步优化呢？

        在题目下方的“提示”中，我们不难找到一些暗示

        很好，我们可以通过将每次幂运算的数据存入到数组，在进行更高次运算时，只需调用之前已经存储过的数据，便能省去一大半的运算次数。

那么，如何才能将一个极大的数进行高效拆解呢？

        要是这个数能用更简单的形式来呈现就好了...更简单？储存一个数，最为简单的形式...没错，是 二进制。

        例如，通过将数字 8 拆解为二进制的 100 ，我们会发现，原本的 \sum^8_1，共8次的运算，可以简化为 2^3，便只有3次了。 现在的效果貌似并不显著，可如果这个数字更大一些呢？

        我们知道，2^{31}已经是一个天文数字，可即便是这样庞大的数据，处理起来也仅仅需要31次运算。

But这个计算过程应该如何用计算机能理解的方式表示出来呢？

        首先，我们可以将题目中的 b 用二进制数表示出来。如 44 这个数字，用二进制表示则为：

44 \ (10) = 101100 \ (2)

        让我们从右往左看，即将这个二进制数倒过来： 001101。 这个式子所表达的意义对解决本题将很有效果：

44 = 0\times2^0+0\times2^1+1\times2^2+1\times2^3+0\times2^4+1\times2^5

        即：

44=2^2+2^3+2^5

        可见，0 和 1 所对应的是 2^n 所乘的系数，而需要注意的是，2^n 应当从 2^0 开始算起。

        所以，由上述推理过程可知：

n^{44}=n^{2^2+2^3+2^5}=n^{2^2}\cdot n^{2^3}\cdot n^{2^5}

        那么，话不多说，我们上代码：

#include<stdio.h>
long long a,b,p;//定义a,b,p为long long型，预防边界溢出
long long ksm(long long base,long long n){ //ksm => 快速幂（很潦草的命名）
    int ans = 1; //将ans的初始值定为1，便于进行乘法运算
    while(n){    //在while函数中将b拆分为二进制数
        if(n&1)  //判定在二进制下，n的末尾是否为0
            ans = ans*base%p;  //一步一模
        base = base*base%p;    //继续一步一模
        n >>= 1;    //等效于 n/=2
    }
    return ans%p;   //返回最终的ans
}
int main(){
    scanf("%lld%lld%lld",&a,&b,&p);
    printf("%lld",ksm(a,b));
    return 0;
}