自动搬运

查看原文

来自洛谷，原作者为

	liangbob 我们生活在大地上，但我们的梦想超越天空。

搬运于2025-08-24 22:42:44，当前版本为作者最后更新于2022-11-14 17:43:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

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

• Q：方法太复杂了，没必要！

  A：是的，我承认自己当时的考场做法确实较为复杂，相比其他人的做法来看，这个做法显得臃肿而多余。但是我还是想说：这也不失为一种方法。学习 OI，接受一种比较复杂的新思路也是重要的，万一后面这种思想可以被用于其它题目呢？

• Q：判断 $a^b$ 是否小于 $0$，小于 $0$ 代表溢出。看看它溢不溢出就行了。

  A：请注意：带符号整数溢出在 C++ 中是未定义行为，这意味着编译器可以随意地处理这种行为，比如，编译器返回 $114514$ 代表溢出也是可以的，所以这种做法有风险，虽不失为一种方法，但在考场上使用务必谨慎。

• Q：特判 $a$ 时需考虑 $b$ 是否大于1，特判 $b$ 时需考虑 $a$ 是否大于 $1$ 吗？

  A：不需要。请注意当 $a$ 或 $b$ 等于 $1$ 时，根据数据范围和 $1^x=1$ 可以肯定答案不会超过 $10^9$。

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 \le 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;
}