【单层循环累加与倍增递推】GESP一级题解：luogu-B4574 [GESP202609 一级] 棋盘上的奖赏

CCF GESP 2026年9月认证（第十五次认证）C++ 一级编程题第二题，洛谷 B4574。本题取材于数学史与计算机科学中极其著名的“国际象棋麦粒问题（Wheat and Chessboard Problem）”，全面考察了 CCF GESP 一级考纲中的核心考点——单层 for / while 循环结构、变量步进累加（Accumulation）、倍增递推思想以及整型数据范围防溢出规范。题目从经典的指数爆炸模型切入，兼具趣味性与考纲规范性。题目难度等级为入门（难度评级★☆☆☆☆）。

B4574 [GESP202609 一级] 棋盘上的奖赏

🔗 洛谷原题传送门：luogu-B4574 [GESP202609 一级] 棋盘上的奖赏

题目要求

题目描述

相传古印度舍罕王为了奖赏宰相西萨发明国际象棋，西萨提的任何要求舍罕王都愿意满足。西萨只求在棋盘第 1 格放 1 粒麦子，第 2 格放 2 粒麦子，之后每一格都放前一格两倍的麦子，以此类推直到第 64 格。国王觉得这奖赏微不足道，立刻命人取粮。

然而麦子的数量飞速增长：到第 20 格已需上百万粒，到第 40 格就耗尽了全国库存，而后面仍有 24 格。最终国王发现，即便倾尽天下粮食也填不满棋盘。

聪明的你知道前 $n$ 格总共需要多少粒麦子吗？

输入格式

一行，一个整数 $n$。

输出格式

一行，一个整数，表示前 $n$ 格总共需要的麦子粒数。

输入输出样例

样例输入 #1

3

样例输出 #1

7

样例输入 #2

10

样例输出 #2

1023

说明/提示

对于 $40\%$ 的测试点，保证 $1 \le n \le 10$。

对于所有测试点，保证 $1 \le n \le 30$。

题目分析与解题思路

1. 麦粒增长规律与数学模型

根据题意，棋盘中每一个格子所放置的麦粒数呈现出经典的等比数列分布：

• 第 $1$ 格：$1$ 粒，即 $2^0$；
• 第 $2$ 格：$2$ 粒，即 $2^1$；
• 第 $3$ 格：$4$ 粒，即 $2^2$；
• ……
• 第 $i$ 格：$2^{i - 1}$ 粒。

题目要求计算的是前 $n$ 格麦子的总和（即数列前 $n$ 项和 $S_n$）：

$S_n = 1 + 2 + 4 + \dots + 2^{n - 1} = \sum_{i=1}^{n} 2^{i-1}$

根据等比数列求和公式（首项 $a_1 = 1$，公比 $q = 2$）：

$S_n = \frac{a_1(1 - q^n)}{1 - q} = \frac{1 - 2^n}{1 - 2} = 2^n - 1$

验证样例：

• 当 $n = 3$ 时：$S_3 = 2^3 - 1 = 8 - 1 = 7$，与样例 1 完全吻合；
• 当 $n = 10$ 时：$S_{10} = 2^{10} - 1 = 1024 - 1 = 1023$，与样例 2 完全吻合。

2. 一级考纲的教学解法：单层循环累加

在 GESP 一级阶段，核心考查的是基础语句与**单层循环（for 循环）**的编写。我们可以模拟放麦子的全过程：

1. 定义变量 total = 0，用于累加所有格子的麦粒总数；
2. 定义变量 current = 1，表示当前格子里应当放置的麦粒数（初始第 1 格为 1）；
3. 循环变量 $i$ 从 $1$ 循环到 $n$：
   • 将当前格子的麦粒加到总数中：total += current;
   • 为下一格做准备，麦粒数翻倍：current *= 2;
4. 循环结束后输出 total。

3. 数据范围与整型防溢出核算

题目给出数据范围：$1 \le n \le 30$。

• 当 $n = 30$ 时： $S_{30} = 2^{30} - 1 = 1,073,741,823 \approx 1.07 \times 10^9$
• 标准 32 位有符号整型 int 的最大上限约为 $2.14 \times 10^9$（$2^{31} - 1 = 2,147,483,647$）。
• 虽然 $1.07 \times 10^9$ 在 int 上限之内，但在循环更新过程中，若 $n$ 稍大或中间变量乘 2，极其容易发生符号位溢出。
• 最佳规范：在信奥与考级中，凡是涉及倍增、幂次或累加求和的问题，一律养成使用 64 位整型 long long 的良好习惯，从根本上杜绝潜在溢出风险。

完整参考代码 (C++11)

/**
 * Problem: luogu-B4574 [GESP202609 一级] 棋盘上的奖赏
 * Standard: C++11 (CCF GESP 官方大纲推荐标准)
 * Author: OneCoder
 */

#include <iostream>

using namespace std;

int main() {
    // 快速输入输出加速
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) {
        return 0;
    }

    // total 存储前 n 格麦粒的总数，current 存储当前格的麦粒数
    // 均选用 64 位有符号整型 long long 防范数值溢出
    long long total = 0;
    long long current = 1; // 第 1 格放入 1 粒麦子

    // 单层循环：依次模拟计算第 1 格到第 n 格
    for (int i = 1; i <= n; ++i) {
        total += current;  // 将当前格麦粒累加至总和
        current *= 2;      // 之后每一格都放前一格两倍的麦子
    }

    // 输出总麦粒数
    cout << total << "\n";

    return 0;
}

方法拓展：位运算极速解法

因为前 $n$ 格麦粒总和严格等于 $2^n - 1$，在 C++ 中，$2^n$ 可以直接借助左移位运算符 1LL << n 进行 $\mathcal{O}(1)$ 极速计算：

#include <iostream>

using namespace std;

int main() {
    int n;
    if (cin >> n) {
        // 1LL 表示 64 位 long long 类型的数值 1，左移 n 位即为 2^n
        cout << (1LL << n) - 1 << "\n";
    }
    return 0;
}

注意：必须使用 1LL 而非 1，因为 1 << 30 默认以 32 位整型进行移位，1 << 31 就会产生未定义行为或负数溢出。使用 1LL 可确保 64 位安全移位。

复杂度分析

• 时间复杂度：
  • 循环模拟法：$\mathcal{O}(n)$。循环执行 $n$ 次，在 $n \le 30$ 条件下仅执行 30 次操作，耗时小于 $0.1\text{ ms}$；
  • 位运算法：$\mathcal{O}(1)$。单条 CPU 移位与减法指令瞬间完成。
• 空间复杂度：$\mathcal{O}(1)$。仅开辟两个 64 位标量变量，内存开销可忽略不计。

考点归纳与避坑提醒

1. 初始值设定：第 1 格麦子是 1 粒而不是 0 粒；
2. 循环累加顺序：必须先加当前格的麦粒数 total += current，再将当前格乘 2 current *= 2 为下一格做准备，千万不能颠倒；
3. 整型常量后缀：若使用位运算，牢记 64 位整数字面量后缀 LL。