快速幂（java）

快速幂（又称二进制取幂）是一种高效计算 a^bmodm 的算法，核心是将指数 b 转化为二进制，通过 “分治 + 迭代” 减少乘法次数，时间复杂度从朴素算法的 O(b) 优化至 O(log2b)，适用于 b 极大的场景。

当指数为偶数时 底数平方 指数除2

当指数为奇数是 ans*底数再将底数平方指数整除2
(x×y)modm=[(xmodm)×(ymodm)]modm），防止数值溢出（尤其适用于大整数场景）。

• • 若当前 b 的最低位为 1（b&1==1），则 ans = (ans * a) % m（累乘当前幂次）。
  • 将 a 平方并取模（a=(a*a)），对应二进制位左移一位（幂次翻倍）。
  • 将 b 右移一位（b=b>>1），处理下一位二进制。（相当于指数除2）

public class FastPower { // 计算 (a^b) % c 的快速幂算法
public static long fastPower(long a, long b, long c) {
long ans = 1; // 先对底数取模，避免初始值过大 a = a % c;
// 当指数大于0时循环
while (b > 0) {
// 如果指数的二进制最后一位是1，将当前底数乘到结果中
if ((b & 1) == 1) {
ans = (ans * a) % c;
} // 底数自乘（相当于指数二进制位右移一位后的权值）
a = (a * a) % c;
// 指数右移一位（二进制角度）
b = b >> 1;
}
return ans;
}
// 测试示例
public static void main(String[] args) {
// 示例：计算 2^10 % 1000 = 24
System.out.println(fastPower(2, 10, 1000)); // 输出 24
}
}
当指数为偶数时 底数平方 指数除2
当指数为奇数是 ans*底数再将底数平方指数整除2

为了避免负数的情况先加上一个mod再进行取余