GESP 八级 · GESP 202606 C++ 八级 第 5 题

下列程序输出的值为（ ）。

#include <iostream>
using namespace std;
long long qpow(long long a, long long b, long long mod) {
    long long ans = 1 % mod;
    while (b) {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main() {
    cout << qpow(3, 20, 17) << endl;
    return 0;
}

看到快速幂模板 → 二进制位展开计算

误判 b&1 为普通除 2；忽略 ans=1%mod 初始化；未每步取模导致溢出。

考点：快速幂｜位运算｜取模运算

解析

3^20 mod 17 按二进制位展开：20(10100)→10→5→2→1，奇数位触发乘入，逐次平方取模得 13。