快速幂计算
学习地址:https://www.bilibili.com/video/BV16Z4y1M7y1/?spm_id_from=333.337.search-card.all.click&vd_source=fd479576740a013e7a8e2c54b5c901eb
快速幂的基本思想:求a的n次方,把a的二进制数,每个为1的位的数加起来,如下图所示:
代码过程:先初始化结果r,每次判断二进制末位是不是1,是的话将结果和a相乘,每次循环都将a和a相乘,然后将n除2向下取整,也就是将二进制数右移1位。
加上取模运算的代码:
例题:
2961. 双模幂运算