CSP-S 2025 第一轮 第33题：程序阅读第 3 题 · 第 6 小题

题目

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define ll long long
int n, m;
std::vector<int> k, p;
inline int mpow(int x, int k) {
    int ans = 1;
    for (; k; k >>= 1, x = x * x) {
        if (k & 1)
            ans = ans * x;
    }
    return ans;
}
std::vector<int> ans1, ans2;
int cnt1, cnt2;
inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) {
    if (l > r) {
        ++cnt;
        ans.push_back(v);
        return;
    }
    for (int i = 1; i <= m; ++i) {
        dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
    }
    return;
}
std::vector<int> cntans1;
int main() {
    scanf("%d%d", &n, &m);
    k.resize(n + 1);
    p.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &k[i], &p[i]);
    }
    dfs(ans1, cnt1, 1, n >> 1, 0);
    dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
    std::sort(ans1.begin(), ans1.end());
    int newcnt1 = 1;
    cntans1.push_back(1);
    for (int i = 1; i < cnt1; ++i) {
        if (ans1[i] == ans1[newcnt1 - 1]) {
            ++cntans1[newcnt1 - 1];
        } else {
            ans1[newcnt1++] = ans1[i];
            cntans1.push_back(1);
        }
    }
    cnt1 = newcnt1;
    std::sort(ans2.begin(), ans2.end());
    int las = 0;
    ll ans = 0;
    for (int i = cnt2 - 1; i >= 0; --i) {
        for (; las < cnt1 && ans1[las] + ans2[i] < 0; ++las)
            ;
        if (las < cnt1 && ans1[las] + ans2[i] == 0)
            ans += cntans1[las];
    }
    printf("%lld\n", ans);
    return 0;
}

本题所求出的是（ ）。

选项

• A. 满足 $a, b, c \in [1, m]$ 的整数方程 $a^3 + b^3 = c^3$ 的解的数量
• B. 满足 $a, b, c \in [1, m]$ 的整数方程 $a^2 + b^2 = c^2$ 的解的数量
• C. 满足 $x_i \in [0, m]$ 的整数方程 $\sum_{i=1}^{n} k_i \cdot x_i^{p_i} = 0$ 的解的数量
• D. 满足 $x_i \in [1, m]$ 的整数方程 $\sum_{i=1}^{n} k_i \cdot x_i^{p_i} = 0$ 的解的数量

答案

D

题解

答案是 D。这段程序用“折半枚举”统计方程 \[ \sum_{i=1}^{n} k_i x_i^{p_i}=0,\qquad x_i\in[1,m] \] 的整数解数量。

抓住下面三个关键点就能读懂：

1. mpow(x, k) 计算 \(x^k\)

它使用快速幂，因此 mpow(i, p[l]) 就是 \(i^{p_l}\)。

1. dfs 枚举变量取值，并记录部分和

核心代码是： ``cpp for (int i = 1; i <= m; ++i) dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l])); ` 这里的循环变量 i 表示 \(x_l\) 的取值，所以 每个变量取 \(1\) 到 \(m\)，不包含 \(0\)。递归结束时，记录的 v` 为 \[ \sum_{j=l_{\text{初始}}}^{r} k_j x_j^{p_j}. \]

1. 将前后两半的和配对，统计总和为零的情况

两次 dfs 分别生成前半部分的和 ans1、后半部分的和 ans2。随后寻找： ``cpp ans1[las] + ans2[i] == 0 ` 也就是整个方程成立的情况。cntans1` 保存前半部分每种和出现的次数，确保不同取值组合都被计入；后半部分的重复和则会逐个遍历。

因此，C 的取值范围不对；A、B 只是特定系数和指数下的方程，不能代表这段程序的一般功能。选 D。