CSP-S 2026 第一轮 第 15 题：执行 power(2, 100, 1000) 调用下列函数，返回值是

题目

执行 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;
}

选项

• A. 576
• B. 376
• C. 976
• D. 176

答案

B

题解

答案是 B. 376。

这段代码是快速幂取模，计算的是 \(a^b\bmod p\)，所以本题求 \(2^{100}\bmod1000\)。

循环中：

• b & 1：判断 b 是否为奇数，若是，就把当前 a 乘进 r，并取模。
• a = a * a % p：将 a 平方后取模。
• b >>= 1：将 b 除以 2，向下取整。

初始 r = 1，逐轮计算如下（a、b 为本轮开始时的值）：

随后 b 变为 0，循环结束，返回 376。