2022 乘方 · 方案二快速幂加封顶

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 2/5 · 共 987 字

指数按二进制拆，乘法结果封顶防溢出

2022
快速幂

正文

// CSP-J 2022 复赛 T1 · 乘方（方案二）
// 原题：https://oj.yecheng.tv/p/CSPJ2022A
//
// 方案二 · 快速幂 + 乘法封顶
// 把指数 b 按二进制拆开：底数不断平方，b 的第 i 位是 1 就把对应的幂乘进答案。
// 这样只需要 O(log b) 次乘法（不超过 31 次），哪怕 b 是 1e9 也毫无压力。
// 配套的防溢出技巧：写一个 mul(x, y)，一旦算出来会超过 1e9，
// 就统一返回 1e9 + 1 这个「代表超了」的哨兵值，之后怎么乘都还是它。

#include <bits/stdc++.h>
using namespace std;

const long long LIM = 1000000000LL;

long long mul(long long x, long long y) {
    if (x > LIM || y > LIM) return LIM + 1;      // 已经是哨兵，保持超了的状态
    if (x > LIM / y) return LIM + 1;             // 用除法预判，避免真的溢出
    return x * y;
}

int main() {
    freopen("pow.in", "r", stdin);
    freopen("pow.out", "w", stdout);

    long long a;
    int b;
    cin >> a >> b;

    long long ans = 1;
    long long base = a;
    while (b > 0) {
        if (b & 1) ans = mul(ans, base);         // 这一位是 1，乘进答案
        b >>= 1;
        if (b) base = mul(base, base);           // 底数平方，准备下一位
    }

    if (ans > LIM) cout << -1 << "\n";
    else cout << ans << "\n";
    return 0;
}

2022 乘方 · 方案二 快速幂加封顶

正文

CSP-J 标程 · 复赛真题的其它内容

2022 乘方 · 方案二快速幂加封顶