题解 P1226 【【模板】快速幂||取余运算】

· · 题解

这篇题解我本来是不打算写的，但是为了各位和我自己，于是就写了这篇题解。

有兴趣的同学们可以去看我P1313的题解：P1313 计算系数

顺便......

求管理员大大通过！！！

（不正经结束）

感谢Kingod——Andy发现文中一处错误

                                分  割  线

基本铺垫

指数运算法制

这一部分必须铺垫，否则后面会听不懂

设一个数a自乘b次叫做a^b

那么：

a^b*a^c=a^{b+c}

解释：b个a和c个a乘在一起，就是b+c个a乘在一起

第一部分铺垫完成！

位运算

位运算指的是对于一个数的二进制进行的操作，下面简单介绍一下几个简单运算符。

左移/右移（<<和>>)

比如说设一个数p为23，它的二进制是10111。

">>"就是右移符号，它是将整个数的二进制表示向右移n位，空位自动补零。

比如p>>1就是p的二进制表示向右移一位。

从10111变成01011。

"<<"就是左移符号，它是将整个数的二进制表示向左移n位，空位自动补零。

比如p<<1就是p的二进制表示向左移一位。

从10111变成101110

逻辑运算

按位或（|）

就是将两个二进制数每一位进行或的逻辑操作，这里简单写一下：

1或1=1 0或1=1 1或0=1 0或0=0

比如说a=10,b=23,a|b的竖式如下：

10111

01010

11111

所以a|b就是31.

按位与(&)

就是将两个二进制数每一位进行与的逻辑操作，这里简单写一下：

1与1=1 0与1=0 1与0=0 0与0=0

比如说a=10,b=23,a&b的竖式如下：

10111

01010

00010

所以a&b就是2.

铺垫完成！！！

                                分  割  线

基本求幂

这个大家肯定都会，设一个初始的ans为1，一个循环b次的循环

将ans不停乘以n，就好了

简朴版代码：

#include<cstdio>
int main(){
    long long b,p,k;
    scanf("%lld%lld%lld",&b,&p,&k);
    long long ans=1;
    for(int i=0;i<p;i++){
        ans=((ans%k)*(b%k))%k;//记得边除边模，要不然少很多个点的分
    }
    ans=ans%k;//记住最后还要取一次模，要不然少最后一个点的分
    printf("%lld^%lld mod %lld=%lld",b,p,k,ans);
    return 0;
}

（分数：84，第六个点TLE）

这看起来很不错了，但是你就是没办法AC...没办法AC...法AC...AC

Aaaaaaaa好烦啊！！！

（我：没错就是这么烦【奸笑】）

好吧，O（N）绝对是没法优化的，那有没有办法降低时间复杂度呢？答案是有的！

伪·第一种优化

从小老师就教我们：降复杂度肯定要降一个级别（废话），这里我就排个级别大小：

（对，我就是边写题解边排的，chen_zhe不要打我TOT）

从这些函数图像上面可以看出它的增长趋势的变化，所以排序简单明了(P为指数）：

O_{(P)} > O_{(\sqrt{P})} >O_{(logP)}

然后思考怎么优化成O_{(\sqrt{P})}

然而没想出来怎么优化成O_{(\sqrt{P})}

所以就转攻O_{(logN)}了

某Luogu新手：快进入正题！

真·第一种优化

所以怎么办呢？

log永远和2有关，所以就先看看把P/2会变成什么？

b^P=b^{\frac{P}{2}} * b^{\frac{P}{2}} * b^{P\%2}

嗯，很好，那P/2也可以再分，就可以递归了，这是大好消息！可以解决TLE的问题！

AC代码奉上：

#include<cstdio>
long long B,P,K;
long long qpow(int base,int p){
    if(p==1){
        return base;
    }else if(p==0){
        return 1;
    }else{
        long long ans=qpow(base,p/2)%K;
        long long ans1=(ans%K*ans%K)%K;
        if(p%2==1){
            ans1=(ans1%K*base%K)%K;
        }
        ans1=ans1%K;
        return ans1;
    }
} 
int main(){
    scanf("%lld%lld%lld",&B,&P,&K);
    long long ans=qpow(B,P);
    ans=ans%K;
    printf("%lld^%lld mod %lld=%lld",B,P,K,ans);
    return 0;
}

真·第二种优化

都说了log与2有关，那能不能用二进制进行运算？

把P分解成二进制，就也是log的运算了！

那怎么算呢？

一个二进制数肯定是由0或1表示的，他每一位都有一个权值。

比如说p是23，他的二进制形式是10111，表示如下：

(10111)_2=1*2^4+0*2^3+1*2^2+1*2^1+1*2^0

没毛病，对不对？

那大家看一下2右上角的指数变化是什么样子的？

是不是每次递增一？

对于每次增加一，是不是意味着这个数是乘2？

比如这个：1*2^0*2=1*2^1(1*2=2)

那么他对于b^P有什么意义呢？

或者换一句话说，b^P和b^{2P}的大小有什么差别？

当然是b^P*b^P=b^{2P}了！

那么也就是说，在每次访问这个数的二进制最后一位时，

如果是1，那就乘上b^{2^n}，这个可以用一个变量tmp来记录；

在此之后，tmp自乘，来增加权值。

如果不是，那就对tmp单独操作，进行自乘，将b^{2^n}变成b^{2^{n+1}}

大功告成！

我知道这很难理解，但是希望大家能够把这一部分多看几遍，理解深刻一些。

AC代码奉上：

#include<cstdio>
long long B,P,K;
long long qpow(int base,int p){
    long long ans=1,tmp=base;//从底数开始乘，不停自乘
    while(p!=0){//指数不是0 
        if(p&1){
            ans=(ans%K*tmp%K)%K;
        } 
        tmp=(tmp%K*tmp%K)%K;//自乘
        p=p>>1;//访问下一位 
    } 
    ans=ans%K;
    return ans;
} 
int main(){
    scanf("%lld%lld%lld",&B,&P,&K);
    long long ans=qpow(B,P);
    ans=ans%K;
    printf("%lld^%lld mod %lld=%lld",B,P,K,ans);
    return 0;
}