[CSP-J 2022] 乘方

题意

给出两个正整数 a, b。
如果 $a^b$ 不超过 $10^9$ ，输出它的精确值；否则输出 -1。

思路

先看一个可以直接验证想法的朴素解：

从 1 开始，连续乘上 a 共 b 次。
每乘一次就检查当前结果是否已经超过 $10^9$ ，如果超过就输出 -1。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll LIMIT = 1000000000LL;

ll a, b;

void solve() {
    ll ans = 1;
    for (ll i = 1; i <= b; i++) {
        if (ans > LIMIT / a) {
            cout << -1 << '\n';
            return;
        }
        ans *= a;
        if (ans > LIMIT) {
            cout << -1 << '\n';
            return;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a >> b;
    solve();

    return 0;
}

乍一看，题目里的 b 可以到 10^9，好像不能真的连乘这么多次。

但这里有一个更重要的条件：题目并不要求算出很大的幂。只要结果超过 $10^9$ ，就立刻输出 -1。

如果 a = 1，那么无论 b 多大，答案都是 1。

如果 a >= 2，连续乘法增长非常快：

乘法次数	最小可能结果
10 次	$2^{10}=1024$
20 次	$2^{20}=1048576$
30 次	$2^{30}=1073741824>10^9$

也就是说，只要 $a\geqslant 2$ ，如果答案会超界，最多乘 30 次左右就能发现；如果 30 次左右还没超界，那说明 b 本身也不会很大。

所以正式做法仍然是连续乘，只是在每次乘之前先判断是否会超过上界：

如果 $x>\text{LIMIT}/y$ ，就说明 x * y 一定超过 LIMIT
这时直接输出 -1
否则再执行乘法

正式做法就是：

如果 a = 1，直接输出 1。
从 ans = 1 开始，尝试乘 b 次 a。
每次乘之前检查 $ans > 10^9 / a$ 。
如果会超界，立刻输出 -1。
如果循环正常结束，输出 ans。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll LIMIT = 1000000000LL;

ll a, b;

void solve() {
    if (a == 1) {
        cout << 1 << '\n';
        return;
    }

    ll ans = 1;

    // 只要中途超过 1e9，最终答案就已经确定为 -1。
    // 当 a >= 2 时，最多乘约 30 次就会超过 1e9，不会真的循环到 1e9 次。
    for (ll i = 1; i <= b; i++) {
        if (ans > LIMIT / a) {
            cout << -1 << '\n';
            return;
        }
        ans *= a;
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a >> b;
    solve();

    return 0;
}

复杂度

时间复杂度可以看成 $O(\min(b,30))$ 。更一般地说，是 $O(\min(b,\log\text{LIMIT}))$ 。

空间复杂度是 $O(1)$ 。

总结

这题不是快速幂模板题，关键是“有限上界下的截断计算”。

要点只有两个：

不需要知道超过 10^9 后具体是多少；
每次乘之前判断是否会超界，超界就立刻停止。

目录

题意

思路

代码

复杂度

总结