对a的b次方取模
取模肯定是一边算一边取模(防止计算过程的溢出)
所以只考虑实现a的b次方
快速幂
就直接说写法和一些理解:
计算a ^ b,如果把 b 写成2 进制,如13 的二进制 1101,于是3 号位 、2号位、0号位就都是1(就不证明了,去了解一些二进制就会了),那么就可以得到13 = 2^3 + 2^2 + 2^1 = 8 + 4 + 1。所以a ^13 = a^8 * a^4 * a^1。
核心1:
把b转换成二进制,然和将b的二进制数从右到左判断,如果判断为1,则ans乘上当前的次方
eg: 3^5-> 3^(101)–>第零位表为1,则ans就要乘 a^( 2^0 ),然后第一位为0,不操作,第二位为1,ans乘上a^( 2^2)–>ans = 1(ans的初始值) * a^( 2^0 ) (==第一次操作==) * a^( 2^2)(==第二次操作==)
核心2:
每次循环的时候不管要不要对ans进行操作,都要对a进行一次操作,即a = a * a,假如到了第n此循环,此时正在判断b的二进制的第n-1位是否为1。又因为a在第一次进入循环时,为a^1 ,即a^( 2^0) ,那么第n次循环就是a^( 2^n-1),正好b正在判断第n-1位,此时如果为1,则直接将ans = ans * a 即可。
最后还有二进制的一些操作
按位与 &(都为1的时候为1)
按位或 |(有1就变1)
异或 ^ (不同为1,相同为0)
运用:
求n的第k位数字: n >> k & 1(k的第n位为1,则为真)
-n的求法:取反码,然后加1(符号位变为1)
2(010)-> -2(101 + 1 -> 110)
只留下n的最后一位1:lowbit(n) = n & -n
n的最后一个1变为0:n&(n - 1)
最后注意取模
代码
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
int a, b, p, ans = 1;
cin >> a >> b >> p;
ans %= p;
while (b){
if (b & 1 == 1)
{
ans = 1ll * ans * a % p;(乘了1ll(这里一个是数字1和字母l,这个字体显示不好)可以将其转化为longlong)
}
b >>= 1;
a = 1ll * a * a % p;
}
cout << ans << endl;
return 0;
}