【模板】快速幂

题目

洛谷P1226快速幂||取余运算

题解

b&1表示b在二进制下的最低位。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月12日 上午8:48

【小白解析】
任何十进制数字都可以写作二进制,换言之是用2的不同幂之和表示。因而形如5^5的数即可表示成5^(101bin),即5^(2^2+0+2^0)=5^(2^2)*5^(2^0)。不难看出,仅当二进制表示下某一位为1时,该位才成为指数乘积的一部分。第10行的if(b&1)判断意义便在此。
其余运算均为数论基础。
*话说是否可以把a%p当作quick()的第一个参数输入?虽然好像没有什么影响。