【快速幂】

【快速幂】

推荐视频链接
推荐好文
注：只是新手的笔记，慎看！！！欢迎大佬指错

求 aⁿ怎样写呢？
可以先定义一个cns=1再用一个for循环每次让cns*=a对吧
但是这样时间复杂度就是**O(n)**了，毕竟只是一个小运算，时间复杂度还是有点高了对吧
于是，便引出了快速幂

啥是快速幂？
我们知道，一个数可以转为二进制，如13=1101
怎么来的？
13=1x2³+1x2²+0x2¹+1x2⁰=8+4+0+1
于是，2¹³便可以写成2¹¹⁰¹进一步写成 2^8+4+0+1即2⁸x2⁴x2¹

那问题就来了，怎样把一个数弄成二进制？
我们可以对一个数 如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;}