Count Equation Solutions 题解

XuYueming / 2024-09-24 / 原文

前言

题目链接：洛谷；UVA。

题意简述

求以下方程解的个数：

\[a_1 x_1 - a_2 x_2 + a_3 x_3 - a_4 x_4 + a_5 x_5 - a_6 x_6 = 0 \]

其中 $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;
}