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

题目

#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;
}

当输入为 3 15 1 2 -1 2 1 2 时，输出结果为（ ）

选项

• A. $4$
• B. $8$
• C. $0$
• D. $10$

答案

B

题解

选 B，输出为 \(8\)。

这段程序统计的是：让每个变量在 \(1\) 到 \(m\) 中取整数，满足 \[ k_1x_1^{p_1}+k_2x_2^{p_2}+\cdots+k_nx_n^{p_n}=0 \] 的方案数。

代入输入，得到 \(n=3,m=15\)，三个系数、指数分别为 \((1,2),(-1,2),(1,2)\)，所以要求 \[ x_1^2-x_2^2+x_3^2=0 \quad\Longleftrightarrow\quad x_1^2+x_3^2=x_2^2, \] 其中 \(1\le x_1,x_2,x_3\le15\)。

也就是找三条边都不超过 \(15\) 的整数直角三角形：

两条直角边可以交换位置。例如第一组对应 \((x_1,x_2,x_3)=(3,5,4)\) 和 \((4,5,3)\)，是两种不同方案。

因此共有 \(4\times2=\boxed{8}\) 种。