【题解】P8813 题解

· · 题解

2023 年 10 月 15 日更新：增加注释，修改错误的代码。感谢 hexuchen 大佬指出。

2024 年 7 月 31 日更新：没想到两年前写的题解能被这么多人看到，也非常感谢各位的支持！现在评论区中提出了一些问题，这里就这些问题统一回答，并对评论区中有价值的建议对题解进行了修改。

2025 年 2 月 15 日更新：再次回看自己原来的做法（下文中的方法一）发现还是太吃操作了，于是补充了一种简单而强势的方法。上述回答针对的是第一种做法。

2025 年 3 月 6 日更新：根据评论区中的意见再次加入了一种代码量极小做法，感谢 Clovtong 大佬提出这种做法。

2025 年 4 月 27 日更新：更新了一些描述和代码，感谢 __orange__ 大佬指出这个细节问题。

P8813 题解

方法一（考场做法）

思路分析

这道题主要是特判。

首先我们发现，\left\lfloor\\\sqrt{10^9}\right\rfloor = 31622 ，\left\lfloor\\\log_2{10^9}\right\rfloor = 29。即 a > 31622 或 b > 29 时必定大于 10^9。但是注意这是在满足 a, b \geq 2 时才有的结论。所以注意特判 a = 1 和 b = 1，a = 1 时直接输出 1 ，b = 1 时直接输出 a。

但是余下的怎么办呢？显然，当 \dfrac{10^9}{a^n} < a 时，说明 a_n \cdot a = a^{n+1} > 10^9。依此判断即可。由于此时 b \le 29，大于 29 的情况已经被特判掉了，于是直接暴力计算就行。

代码

#include <iostream>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    //特判 
    if(a == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    if(b == 1)
    {
        cout << a << endl;
        return 0;
    }
    if(a > 31622)
    {
        cout << -1 << endl;
        return 0;
    }
    if(b > 29)
    {
        cout << -1 << endl;
        return 0;
    }
    long long fac = 1;
    for(int i = 1;i <= b;i++) //i 表示准备乘上第 i 个 a 
    {
        if((1e9 / double(fac)) < a) //准备乘上的时候看看是否超出限制 
        {
            cout << -1 << endl;
            return 0;
        }
        fac *= a;
    }
    cout << fac << endl;
    return 0;
}

方法二（更为简洁的做法）

思路分析

考虑到 a \le 10^9。

假设 a^{x} \le 10^9，那么 a^{x+1} \le 10^9 \times10^9=10^{18}，也就是说如果一个幂第一次超过 10^9 次方，那么它必然比 10^{18} 次方小，即不超过 long long 的范围。

于是我们直接开一个 long long 类型的变量 x，模拟计算幂的过程，每次给 x 乘上一个 a，当 x 超过 10^9 时，输出 -1，直接结束程序。否则输出 x 就可以了。

我们来分析一下复杂度。当 a \ge 2 时，我们要进行 \log_a 10^9 次循环，可以通过。当 a=1 时，复杂度虽然不正确，但是我们可以特判一下，输出 1 即可。

代码

#include <iostream>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    //特判 
    if(a == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    long long x = 1;
    for(int i = 1;i <= b;i++) //模拟幂运算的过程
    {
        x *= a;
        if(x > 1e9)
        {
            cout << -1 << endl;
            return 0;   
        }
    } 
    cout << x << endl;
    return 0;
}

方法三（pow 函数做法）

方法概述

直接使用 pow 函数计算 a^b 的值并判断。

正确性证明

首先我们来看时间复杂度是否正确。参考 这个问题的回答：

That depends on the underlying architecture. On the most common desktop architecture, x86, this is a constant time operation.

这取决于底层的体系结构。在最常见的桌面体系结构 x86 上，这是一个常数时间操作。

即时间复杂度为 O(1)。由于 pow 函数涉及到浮点数运算，因此常数较大，多次进行有可能会超时。但这里我们只进行一次操作，时间复杂度是正确的。

接着我们来看正确性。双精度浮点数，即 double 类型，它的存储范围约为：[-1.4\times 10^{308},1.4 \times 10^{308}]。

当一个数过小时，这个数会被下溢到 0。但由于本题 a,b\ge 0，不存在这个问题。

当一个数过大（超过储存范围）时，这个数会上溢成 \inf，此时在代码上判断 10^9 次方是否小于这个数结果一定为真，而实际上也确实小于，因此是正确的。

同时 pow 的运算会存在严重的精度缺失问题。但是由于 a,b \le 10^9 次方，范围相对较小，而且我们的目的是判断是否大于 10^9 次方。在这么一个小范围的前提下，这么判断并不会出错。具体的可以参考 这篇题解。

于是，我们可以认为，这么做是正确的。

代码

在实现代码时需要注意，当且仅当 x=a^b 的数据类型为 double 时，与 x 进行比较才会具有上述性质。如果 x 为整数类型，赋值后 x 可能会溢出。

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    double x = pow(a, b);
    cout << int(x > 1e9 ? -1 : x) << endl;
    return 0;
}