2022真题 | 乘方 luogu-P8813

CSP-J 2022真题-乘方，是一道基础模拟与数值溢出处理的考点。重点考察如何在指数运算中安全地进行溢出判断，以及如何针对特殊边界（如 $a=1$）进行优化以避免超时。适合GESP二级及以上考生练习，难度⭐，洛谷难度等级入门。

P8813 [CSP-J 2022] 乘方

题目要求

题目背景

为模拟赛时得分情况，本题时限降低 50%。

题目描述

小文同学刚刚接触了信息学竞赛，有一天她遇到了这样一个题：给定正整数 $a$ 和 $b$，求 $a^b$ 的值是多少。

$a^b$ 即 $b$ 个 $a$ 相乘的值，例如 $2^3$ 即为 $3$ 个 $2$ 相乘，结果为 $2 \times 2 \times 2 = 8$。

“简单！”小文心想，同时很快就写出了一份程序，可是测试时却出现了错误。

小文很快意识到，她的程序里的变量都是 int 类型的。在大多数机器上，int 类型能表示的最大数为 $2^{31} - 1$，因此只要计算结果超过这个数，她的程序就会出现错误。

由于小文刚刚学会编程，她担心使用 int 计算会出现问题。因此她希望你在 $a^b$ 的值超过 ${10}^9$ 时，输出一个 -1 进行警示，否则就输出正确的 $a^b$ 的值。

然而小文还是不知道怎么实现这份程序，因此她想请你帮忙。

输入格式

输入共一行，两个正整数 $a, b$。

输出格式

输出共一行，如果 $a^b$ 的值不超过 ${10}^9$，则输出 $a^b$ 的值，否则输出 -1。

输入输出样例 #1

输入 #1

10 9

输出 #1

1000000000

输入输出样例 #2

输入 #2

23333 66666

输出 #2

-1

说明/提示

【数据范围与约定】

对于 $10 \%$ 的数据，保证 $b = 1$。
对于 $30 \%$ 的数据，保证 $b \le 2$。
对于 $60 \%$ 的数据，保证 $b \le 30$，$a^b \le {10}^{18}$。
对于 $100 \%$ 的数据，保证 $1 \le a, b \le {10}^9$。

$\text{upd 2022.11.14/2025.04.02}$：各新增加一组 $\text{Hack}$ 数据。

题目分析

本题作为 CSP-J 2022 的第一题，考查的知识点非常基础，主要涉及模拟、幂运算以及对 溢出（Overflow）和时间复杂度（TLE） 的防范与处理。

1. 直观想法与溢出陷阱

求 $a^b$ 最直接的做法是使用一个循环：从 $1$ 循环到 $b$，每次将结果乘以 $a$。 然而，题目中明确指出：当 $a^b > 10^9$ 时输出 -1，并且 $a, b \le 10^9$。

如果我们直接用 long long 甚至 __int128 来强行计算，可能会遇到以下两个关键问题：

• 整型溢出 (Integer Overflow)： 虽然 C++ 中的 long long 最大能表示约 $9 \times 10^{18}$ 的数，但在本题中 $a, b \le 10^9$，如果 $a = 10^9$ 且 $b = 10^9$，其真实结果是一个天文数字，远远超出了任何标准整型（包括 unsigned long long 和 __int128）的表示范围。这会导致数值发生溢出，从而变成一个错误的负数或其它不确定值，使判断条件 ans > 10^9 失效。
• 时间超限 (Time Limit Exceeded, TLE)： 如果 $b$ 很大（比如 $10^9$），直接进行 $10^9$ 次循环的计算在 $1$ 秒（本题甚至时限降低 50% 仅有 0.5 秒）内是绝对会 TLE 的。

2. 优化与避坑策略

为了解决上述问题，我们需要在计算过程中进行实时溢出拦截，并对特殊数据进行特判优化：

策略一：实时溢出拦截

我们不需要等全部乘完再去判断结果是否超过 $10^9$。 在循环相乘的每一步，我们都判断当前的乘积是否已经超过了 $10^9$。一旦超过，立刻停止循环，并输出 -1。

long long temp = ans * a;
if (temp > 1000000000) {
    // 超过 10^9，直接输出 -1 结束程序
}

策略二：特判底数 $a = 1$ 的情况

如果底数 $a = 1$，无论指数 $b$ 有多大，$1^b$ 的结果永远是 $1$。 如果不进行特判，当输入为 1 1000000000 时，程序会尝试循环 $10^9$ 次，从而导致超时。 因此，我们必须在程序开头进行特判：若 $a = 1$，则直接输出 $1$。

为什么 $a \ge 2$ 时循环不会超时？

当 $a \ge 2$ 时，由于 $2^{30} = 1073741824 > 10^9$，这意味着底数至少为 $2$ 时，最多只需要乘 $30$ 次就会超过 $10^9$ 并触发拦截退出。 因此，在 $a \ge 2$ 的情况下，循环次数最多只有 $30$ 次，时间复杂度为常数级 $O(\log(\text{limit}))$，绝对不会超时！

3. 算法流程

1. 读入 $a$ 和 $b$。
2. 特判：如果 $a = 1$，直接输出 $1$ 并结束程序。
3. 声明一个 long long 类型的变量 ans 初始化为 $1$。
4. 循环 $b$ 次：
   • 每次将 ans 乘以 $a$。
   • 检查 ans 是否大于 $10^9$。如果是，输出 -1，并结束程序。
5. 如果循环顺利结束（说明 $a^b \le 10^9$），输出 ans 的值。

示例代码

#include <iostream>

int main() {
    // 优化输入输出流性能
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    long long a, b;
    std::cin >> a >> b;

    // 特判：如果底数 a 为 1，则 1 的任何次方都是 1，直接输出
    // 避免 b 很大时（如 10^9）循环超时
    if (a == 1) {
        std::cout << 1 << "\n";
        return 0;
    }

    long long ans = 1;
    bool overflow = false;

    // 模拟乘方过程
    for (int i = 1; i <= b; i++) {
        ans *= a;
        // 实时检查是否超过 10^9
        if (ans > 1000000000) {
            overflow = true;
            break;
        }
    }

    // 根据是否溢出输出对应结果
    if (overflow) {
        std::cout << -1 << "\n";
    } else {
        std::cout << ans << "\n";
    }

    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号