概述

本题要求对 ~n~ 个形如 ~a_i x_i + b_i = c_i~ 的一元一次方程分别求出解，再回答 ~Q~ 次询问：区间 ~[L, R]~ 内有多少个不同的整数 ~x~ 至少是其中一个方程的解。核心解法是移项得到 ~x_i = (c_i - b_i) / a_i~，把每个解标记进桶中（同一个解重复出现也只标记一次，天然完成去重），再对桶求前缀和，使每次询问在 ~O(1)~ 时间内回答。

分析

核心观察

每个方程的解由系数唯一确定，移项得 ~a_i x_i = c_i - b_i~，即 ~x_i = (c_i - b_i) / a_i~。询问统计的是不同 ~x~ 的个数，同一个 ~x~ 无论被多少个方程命中都只贡献 ~1~，用一个「该值是否出现过」的桶标记即可自动去重。

思路

设第 ~i~ 个方程为 ~a_i x_i + b_i = c_i~，两边同时减去 ~b_i~ 得 ~a_i x_i = c_i - b_i~，于是

$$\displaystyle x_i = \frac{c_i - b_i}{a_i} $$

题面保证每个解 ~x_i~ 都是正整数，且由 ~1 \le |a_i|~ 知 ~a_i \ne 0~，除法总可以进行。

从方程字符串 ~a x \pm b = c~ 中取出三个数是本题唯一的实现难点：~a~ 可以带负号（如 ~-3x+13=10~ 中 ~a = -3~），~b~ 前面的 + 或 − 必须并入 ~b~ 的取值（如 ~4x-8=16~ 中 ~b = -8~，若误读成 ~b = 8~ 便会得到 ~x = 2~ 而不是正确的 ~x = 6~），~c~ 同样可能为负。读入时可以借助 sscanf，把 x 与 = 当作字面字符写进格式串，让三个 ~\%d~ 依次读入 ~a, b, c~，符号由 ~\%d~ 自行处理；也可以手写解析，逐个字符跳过 x 与 =，遇到 + 或 − 时把符号并入紧随其后的整数。

求解结果只需要记录出现性：由 ~1 \le |b_i|, |c_i| \le 2000~ 得 ~|c_i - b_i| \le 4000~，又 ~|a_i| \ge 1~，故解最大可以取到 ~4000~（例如 ~1x-2000=2000~ 的解为 ~4000~）。询问保证 ~R \le 1000~，超过 ~1000~ 的解永远不会落入任何询问区间，因此桶只需覆盖 ~1 \sim 1000~，标记前判断 ~1 \le x \le 1000~ 即可，既不会越界也不会漏计。

记 ~mark[i] = 1~ 表示 ~i~ 至少是一个方程的解，~mark[i] = 0~ 表示不是，并令

$$\displaystyle pre[i] = \sum_{j = 1}^{i} mark[j] $$

则询问 ~[L, R]~ 的答案就是 ~pre[R] - pre[L - 1]~，即区间内被标记的位置个数。若不做前缀和，每次询问直接扫描 ~mark[L \dots R]~ 需要 ~O(n + Q \times 1000)~，在本题 ~n, Q \le 1000~ 的数据范围下同样可以通过；真正的陷阱在于去重，若直接统计「解落在区间内的方程个数」，样例 ~2~ 中 ~x = 3~ 被三个方程命中，会被多算两次。

具体示例

以样例 ~1~ 为例，三个方程 ~2x+4=10~、~-3x+13=10~、~4x-8=16~ 的解依次为 ~x = 3~、~x = 1~、~x = 6~，桶中只有下标 ~1, 3, 6~ 被标记，前缀和在 ~0 \sim 8~ 上的取值为 ~0, 1, 1, 2, 2, 2, 3, 3, 3~。四次询问分别为：~[1, 6]~ 得 ~3 - 0 = 3~，~[1, 8]~ 得 ~3 - 0 = 3~，~[3, 6]~ 得 ~3 - 1 = 2~，~[4, 5]~ 得 ~2 - 2 = 0~，与样例输出一致。

以样例 ~2~ 为例，五个方程的解依次为 ~3, 5, 5, 3, 3~，去重后只有 ~3~ 与 ~5~ 两个位置被标记：~x = 3~ 被三个方程命中、~x = 5~ 被两个方程命中，但都各自只计一次。三次询问 ~[1, 3]~、~[1, 5]~、~[3, 5]~ 的答案分别为 ~1~、~2~、~2~。

算法步骤

1. 读入 n 与 q。
2. 逐个读入方程字符串，解析出三个可带符号的整数 a、b、c，其中 a 的负号、b 前的 + 或 − 都要并入各自的值。
3. 计算 x ~= (c - b) / a~；若 ~1 \le x \le 1000~，把 mark 的第 x 项置为 ~1~（同一个 x 重复出现也只置为 ~1~）。
4. 对 mark 求前缀和，结果存入 pre。
5. 对每次询问读入 L、R，计算 ans ~= pre[R] - pre[L - 1]~ 并输出。

复杂度分析

• 时间：~O(n + 1000 + Q)~。解析 ~n~ 个方程并标记需要 ~O(n)~，求前缀和需要 ~O(1000)~，每次询问为 ~O(1)~。
• 空间：~O(1000)~。桶与前缀和数组各需要约 ~1000~ 个元素，不计输出缓冲。

实现注意事项

• 符号必须跟着数字一起读：~a_i~ 可以带负号，~b_i~ 前的 + 或 − 必须并入 ~b_i~，~c_i~ 同样可能为负。以 ~4x-8=16~ 为例，~b = -8~，解得 ~x = 6~；若把 ~b~ 读成 ~8~，就会算出 ~x = 2~ 这样的错误结果。
• 移项方向不能反：正确式子是 ~x = (c - b) / a~，写成 ~x = (c + b) / a~ 几乎全错。
• 去重要靠桶完成：题目问的是不同 ~x~ 的个数，同一个解只能计一次，直接统计「解落在区间内的方程个数」会在样例 ~2~ 上出错。
• 桶的下标范围要留足：解最大可达 ~4000~，如果桶只开到 ~1000~，标记前必须先判断 ~1 \le x \le 1000~，否则会写到数组外。
• 只标记正整数解：标记条件是 ~x \ge 1~，解为 ~0~ 或负数的方程不应进入桶（本题数据保证解为正整数，此处仅为稳妥）。
• 输入是一行一个方程字符串，用格式化读入时要按 x 与 = 这两个字面字符切分，手写解析则要显式吃掉负号，不要漏掉 ~b~ 前的正号。
• 输出最多约 ~1000~ 行，C++ 应把答案拼成字符串后一次性写出，Python 应先把答案收集到列表再用换行符连接输出，避免逐行刷新缓冲区。
• 询问保证 ~1 \le L \le R \le 1000~，前缀和数组开到下标 ~1000~ 就够用，无需特判 ~L > R~ 或 ~R~ 越过上界的情况。

源代码

#include <cstdio>
#include <string>
#include <vector>

int main() {
    int n = 0, q = 0;
    if (std::scanf("%d%d", &n, &q) != 2) return 0;

    const int MAXV = 1000;  // 询问保证 R <= 1000，更大的解不会被问到
    std::vector<char> mark(MAXV + 1, 0);

    char buf[64];
    for (int i = 0; i < n; ++i) {
        if (std::scanf("%63s", buf) != 1) return 0;
        int a = 0, b = 0, c = 0;
        // 按 'x' 与 '=' 两个字面字符切分，符号由 %d 自动读入
        if (std::sscanf(buf, "%dx%d=%d", &a, &b, &c) != 3) continue;

        int num = c - b;                    // a x = c - b
        if (a == 0 || num % a != 0) continue;
        int x = num / a;
        if (x >= 1 && x <= MAXV) mark[x] = 1;  // 同一个解只标记一次
    }

    std::vector<int> pre(MAXV + 1, 0);      // pre[i] = 1..i 中被标记的个数
    for (int i = 1; i <= MAXV; ++i) pre[i] = pre[i - 1] + mark[i];

    std::string out;
    out.reserve((size_t)q * 6);
    for (int i = 0; i < q; ++i) {
        int L = 0, R = 0;
        if (std::scanf("%d%d", &L, &R) != 2) break;
        out += std::to_string(pre[R] - pre[L - 1]);
        out += '\n';
    }
    std::fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

import sys
import re


def main():
    data = sys.stdin.read().split()
    pos = 0
    n = int(data[pos]); pos += 1
    q = int(data[pos]); pos += 1

    MAXV = 1000                              # 询问保证 R <= 1000
    mark = [0] * (MAXV + 1)

    for _ in range(n):
        a, b, c = map(int, re.findall(r'[-+]?\d+', data[pos]))
        pos += 1
        num = c - b                          # a x = c - b
        if a != 0 and num % a == 0:
            x = num // a
            if 1 <= x <= MAXV:
                mark[x] = 1                  # 同一个解只标记一次

    pre = [0] * (MAXV + 1)                   # pre[i] = 1..i 中被标记的个数
    for i in range(1, MAXV + 1):
        pre[i] = pre[i - 1] + mark[i]

    out = []
    for _ in range(q):
        L = int(data[pos]); R = int(data[pos + 1]); pos += 2
        out.append(str(pre[R] - pre[L - 1]))
    sys.stdout.write('\n'.join(out) + '\n')


main()