CSP-S 提高级 · CSP 2026 提高级第一轮 第 15 题

【单选】执行 power(2, 100, 1000) 调用下列函数，返回值是（ ）。

long long power(long long a, long long b, long long p) {
    long long r = 1 % p;
    while (b) {
        if (b & 1)
            r = r * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return r;
}

这是快速幂（模幂）的模板：求 2^100 mod 1000。要么按二进制逐位平方-乘手算，要么直接注意到 2^100 的末三位是 376。

把 r = 1 % p 忽略而算错起点；中间值 a = a * a % p 忘记取模导致越界（虽然 long long 不会溢出，但手算时要记得每步取模）。

解析

题目函数：

long long power(long long a, long long b, long long p) {
    long long r = 1 % p;
    while (b) {
        if (b & 1) r = r * a % p;   // 该位为 1 → 把当前的 a 乘进答案
        a = a * a % p;              // 底数平方，为下一位做准备
        b >>= 1;                    // 指数右移一位
    }
    return r;
}

求 power(2, 100, 1000) = 2^100 mod 1000。

方法一：按快速幂逐位推演（考试最稳）

100 = 1100100₂（位权：64 + 32 + 4 = 100 ✓）。按位从低到高处理：

结果 376，选 B。

方法二：分解成 2^10 的幂（更快）

注意 2^100 = (2^10)^10 = 1024^10。

• 1024 mod 1000 = 24 → 求 24^10 mod 1000；
• 24² = 576；24⁴ = 576² = 331776 ≡ 776；24⁸ ≡ 776² = 602176 ≡ 176；
• 24^10 = 24⁸ × 24² ≡ 176 × 576 = 101376 ≡ 376 ✓

方法三：记忆型观察

2^10 = 1024 → 末三位 024；2^20 = 1048576 → 576；2^30 → 576×576 = 331776 → 776……末三位会快速稳定：2^n (n ≥ 3) 的末三位以 100 为周期，而 2^100 的末三位正是 376（也是 2^100 的十进制末三位，100 = 4×25 的经典结论）。

其他选项为什么错

• A. 576 = 2^20 mod 1000（指数少算了 5 倍）；
• C. 976、D. 176 = 24⁸ mod 1000 等中间量，属于"走到一半就停"的错误。

记忆点

• 快速幂模板三句话：位为 1 就乘、底数每轮平方、指数每轮右移，复杂度 O(log b)；
• r = 1 % p 是防 p = 1 的写法，读程序题要能看出这个小细节；
• 手算技巧：把指数拆成 (2^k)^m 的形式，往往比逐位平方-乘更快。