Count Equation Solutions 题解

前言

题目链接：洛谷；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;
}