语言月赛 202311 方程求解

题意分析

给定 $n$ 个形如 $a_ix + b_i = c_i$ 的一元一次方程，小 A 想知道在每次给定的区间 $[L, R]$ 内，有多少个正整数 $x$ 是至少一个方程的解。

每次询问输出满足条件的正整数 $x$ 的个数。

---

解题思路

一、方程的处理

每个方程都形如：

$a\cdot x + b = c$

我们可以移项并求解：

\[ x = \frac{c - b}{a} \]

根据题目保证，所有方程的解都是正整数，即 $\frac{c - b}{a}$ 是正整数，且结果大于等于 1。

因此我们可以：

• 遍历所有方程，提取出系数 $a, b, c$。
• 利用上述公式求出对应的 $x$。
• 将求出的所有解 $x$ 存储（例如打标记 vis[x] = 1）。

特别说明：由于题目中字符如 x、+、= 并不影响求解，因此可直接略过，仅关注 a, b, c 三个数值的提取与处理。

for (int i = 1; i <= n; i++)
{
    int a, b, c;
    char op1, op2, op3;
    // 252x+578=10245
    cin >> a >> op1 >> op2 >> b >> op3 >> c;
    int x;
    if (op2 == '+')
        x = (c - b) / a;
    else
        x = (c + b) / a;
    vis[x] = 1;
}

---

二、查询处理

接下来处理 $Q$ 次询问。每次输入一个区间 $[L, R]$，统计该区间内有多少个整数 $x$ 满足 vis[x] = 1。

实现方式非常简单：

• 对于每个询问，从 $i = L$ 到 $R$ 遍历；
• 统计其中有多少个位置满足 vis[i] = 1；
• 统计结果即为本次询问的答案。

---

实现步骤

• 预处理阶段：

  • 遍历 $n$ 个方程；
  • 对每个方程解析出 $a, b, c$；
  • 利用公式 $x = (c - b) / a$ 求出解；
  • 若 $x$ 是正整数（即 $x \geq 1$ 且整除），则打标记：vis[x] = 1。

• 查询阶段：

  • 对于每次询问区间 $[L, R]$：
    • 初始化计数器；
    • 从 $L$ 遍历到 $R$，累加 vis[i]；
    • 输出计数器值。

---

时间复杂度分析

• 预处理方程：$O(n)$；
• 每次查询暴力枚举 $[L, R]$：最坏 $O(1000)$；
• 总体复杂度为 $O(n + Q \cdot 1000)$，其中 $n, Q \leq 1000$，完全可以接受。

---

总结

• 核心是将所有方程的正整数解打标记；
• 每次查询通过暴力枚举区间统计标记次数；
• 利用固定上限范围（$x \leq 1000$）简化实现；
• 本题是典型的“值域有限 + 预处理 + 暴力查询”模型，非常适合入门题型练习。