UVA13262

XuYueming · 2024-09-24 14:00:48 · 题解

前言

题目链接：洛谷；UVA。

更好的体验。

题意简述

求以下方程解的个数：

其中 1 \leq x_i \leq m \leq 10^2，x_i \in \mathbb{Z}，多测。

题目分析

把 a_2, a_4, a_6 变成其相反数，变成 \sum \limits _ {i = 1} ^ 6 a_i x_i = 0，方便讨论。

直接枚举做是 \Theta(m ^ 6) 会超时。不妨考虑折半搜索，对于前 \dfrac{6}{2} = 3 个 x，我们用 \Theta(m ^ 3) 的时间枚举所有可能值，并用一个数据结构记录 \sum \limits _ {i = 1} ^ 3 a_i x_i 的所有可能值。对于后 3 个 x，同样使用 \Theta(m ^ 3) 的时间复杂度枚举，统计答案就是在数据结构中，查询使得 \sum \limits _ {i = 1} ^ 3 a_i x_i + \sum \limits _ {i = 4} ^ 6 a_i x_i = 0 的 \sum \limits _ {i = 1} ^ 3 a_i x_i 的个数，也就是查询有多少 \sum \limits _ {i = 1} ^ 3 a_i x_i = -\sum \limits _ {i = 4} ^ 6 a_i x_i。这个数据结构可以是哈希表。

时间复杂度：\Theta(m^3)。

代码

#include <cstdio>
#include <iostream>
#include <unordered_map>
using namespace std;

int mx, val[6];

signed main() {
    while (~scanf("%d", &mx)) {
        for (int i = 0; i < 6; ++i) {
            scanf("%d", &val[i]);
            if (i & 1) val[i] = -val[i];
        }
        unordered_map<int, int> cnter;
        for (int i = 1; i <= mx; ++i)
        for (int j = 1; j <= mx; ++j)
        for (int k = 1; k <= mx; ++k)
            ++cnter[i * val[0] + j * val[1] + k * val[2]];
        long long ans = 0;
        for (int i = 1; i <= mx; ++i)
        for (int j = 1; j <= mx; ++j)
        for (int k = 1; k <= mx; ++k)
            ans += cnter[-(i * val[3] + j * val[4] + k * val[5])];
        printf("%lld\n", ans);
    }
    return 0;
}