北京化工大学2021年ACM寒假专题训练（一）

问题 A: a^b

 

求 a 的 b 次方对 p 取模的值，其中
输入
三个用空格隔开的整数a,b和p。
输出
一个整数，表示的值。
样例输入
2 3 9
样例输出
8
分析
作为一个只懂Python语言的算法竞赛萌新，，我首先想到的肯定是直接计算么，先算s=a^b,再算s%p,不就OK，毕竟Python支持大整数，直接print(a**b%p)不就可以，但是当ａ，ｂ，ｐ很大时，运算超时了，这种方法是不可取的，这道题考到了快速幂取模。
快速幂
　　首先我们先看一个简单的问题，怎么算，很简单，，２连续乘几下２就出结果了，那呢？那直接再连续乘多个２，就可以了，但是有没有可能减少运算次数呢？
　　可以想到
　　
　　
　　可以经过一次计算得到
　　所以

所以前者需计算15次（），后者计算4次（一次，两次，三次，四次）

将一个数表示成二进制，比如  b   可以为 

那么可为
乘法取模公式　

Python代码实现

 所以根据以上两个公式得到代码

a,b,p=map(int,input().split())
ans=1
while b>0:
    if b&1==1:
        ans*=a%p
    a=a*a%p
    b>>=1
print(ans%p)

 到OJ上测试正确了

那么直接print(a**b%p)呢

a,b,p=map(int,input().split())
print(a**b%p)#注：**表示平方，%表示mod（取模）

测试一下，果然超时了

以上就是我做A题的过程与一些思考。