快速幂 题解

一、问题

计算 a^b mod m。b 最大到 10^9。 如果直接循环 b 次：for i in range(b): result = result * a % m，10^9 次循环直接 TLE

二、核心原理：二分

幂运算有个性质：

$a^8 = (a^4)^2$ ← 算一次 $a^4$，再平方一次就行 $a^9 = a × (a^8)$ ← 奇数的话拆一个 $a$ 出来

每一步把指数对半砍，$10^9$ 只要砍约 30 次就到 1 了

三、算法：快速幂

把指数 b 写成二进制。例如 b = 10：

10 的二进制 $= 1010$ $= 1×8 + 0×4 + 1×2 + 0×1$ $= 8 + 2$

所以 $a$^$10$ $=$ $a^8$ × $a^2$ 只需要两个关键值：$a^2$ 和 $a^8$

四、$a^2$ 和 $a^8$ 怎么得出来？

初始: $a = a^1$

看第 $0$ 位（最低位）: $a = a^1$ 看第 $1$ 位: $a = a^2$ ← 平方 看第 $2$ 位: $a = a^4$ ← 再平方 看第 $3$ 位: $a = a^8$ ← 再平方

b的二进制哪位是 1，就把当前 a 乘进答案

五、手算验证：$2$^$10$ $mod 1000$

b=10，二进制 1010，从低到高看：

最后 result = 1024，mod 1000 = 24

六、代码

a, b, m = map(int, input().split())

result = 1
a = a % m

while b > 0:
    if b % 2 == 1:               # b 的二进制最低位是 1
        result = (result * a) % m
    a = (a * a) % m              # a 平方，准备看下一位
    b //= 2                      # b 右移，砍掉最低位

print(result)

using System;

class Program
{
    static void Main()
    {
        string[] input = Console.ReadLine().Split();
        long a = long.Parse(input[0]);
        long b = long.Parse(input[1]);
        long m = long.Parse(input[2]);

        long result = 1;
        a = a % m;

        while (b > 0)
        {
            if (b % 2 == 1)              // 二进制最低位是 1
                result = (result * a) % m;

            a = (a * a) % m;             // a 平方
            b /= 2;                      // b 右移
        }

        Console.WriteLine(result);
    }
}