【快速幂】
推荐视频链接
推荐好文
注：只是新手的笔记，慎看！！！欢迎大佬指错
求 an怎样写呢？
可以先定义一个cns=1再用一个for循环每次让cns*=a对吧
但是这样时间复杂度就是**O(n)**了，毕竟只是一个小运算，时间复杂度还是有点高了对吧
于是，便引出了快速幂
啥是快速幂？
我们知道，一个数可以转为二进制，如13=1101
怎么来的？
13=1x23+1x22+0x21+1x20=8+4+0+1
于是，213便可以写成21101进一步写成 28+4+0+1即28x24x21
那问题就来了，怎样把一个数弄成二进制？
我们可以对一个数 如13进行位运算&1
位运算&1可以把一个二进制最低位的数表示出来，1&1=1，0&1=0
于是，只要这一位为1，我就得乘这一位的对应2的次方
然后再通过右移运算符>>来逐位查看
代码:
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;inta,n,p;//p为取余intmi(inta,intn){intcns=1;while(n){if(n&1)cns=(cns*a)%p;a=(a*a)%p;n>>=1;}returncns;}signedmain(){cin>>a>>n>>p;return0;}
)
)
