[语言月赛 202311] 方程求解

Luogu

IDLGB3892

Time1000ms

Memory512MB

DifficultyP2

模拟2023O2优化字符串（入门）语言月赛

小 A 有 $n$ 个关于 $x$ 的方程，第 $i$ 个方程形如 $a_ix_i+b_i=c_i$。方程的解 $x$ 均为正整数，例如下面几个方程都是符合要求的方程： ``` 2x+4=10 -3x+13=10 4x-8=16 ``` 其中，第一组方程的解为 $x_1=3$，第二组方程的解为 $x_2=1$，第三组方程的解为 $x_3=6$。小 A 想要知道，给定 $L,R$，在 $L\leq x\leq R$ 的范围内，有多少个正整数 $x$ 满足 $x$ 是其中至少一个方程的解。为了防止你欺骗他，他会询问你 $Q$ 次。 ## Input 第一行输入两个正整数 $n,Q$，分别表示小 A 有的方程数，以及小 A 想要向你询问的次数。第二行开始，往下 $n$ 行，每行一个字符串，描述一个方程。第 $(n+2)$ 行开始，往下 $Q$ 行，每行两个正整数 $L,R$，表示一次询问，即给定 $L,R$，询问在 $L\leq x\leq R$ 的范围内，有多少个正整数 $x$ 满足 $x$ 是其中至少一个方程的解。 ## Output 对于每次询问，输出一行一个整数，表示有多少个在 $L\leq x\leq R$ 的范围内的正整数 $x$，满足 $x$ 是其中至少一个方程的解。 [samples] ## Note **【样例解释】** 对于第一组样例，即为题目中的举例。三组方程的解分别为 $x_1=3,x_2=1,x_3=6$。则： - 对于 $1\leq x\leq 6$ 的范围，有 $3$ 个 $x$ 的取值（$x=1,3,6$）是其中至少一个方程的解； - 对于 $1\leq x\leq 8$ 的范围，同上所述； - 对于 $3\leq x\leq 6$ 的范围，有 $2$ 个 $x$ 的取值（$x=3,6$）是其中至少一个方程的解； - 对于 $4\leq x\leq 5$ 的范围，不存在一个 $x$ 是其中至少一个方程的解； - 因此分别输出 $3,3,2,0$。对于第二组样例，五组方程的解分别为 $x_1=3,x_2=5,x_3=5,x_4=3,x_5=3$。则： - 对于 $1\leq x\leq 3$ 的范围，只有 $x=3$ 满足是其中至少一个方程的解； - 对于 $1\leq x\leq 5$ 的范围，有 $2$ 个 $x$ 的取值（$x=3,5$）是其中至少一个方程的解； - 对于 $3\leq x\leq 5$ 的范围，有 $2$ 个 $x$ 的取值（$x=3,5$）是其中至少一个方程的解； - 因此分别输出 $1,2,2$。 **【数据范围】** 数据保证，$1\leq n,Q\leq 1000$，方程中 $a_i,b_i,c_i$ 满足 $1 \leq |a_i|,|b_i|,|c_i| \leq 2000$，每一组方程的解 $x_i$ 必定为正整数。询问时的 $L,R$ 满足 $1\leq L\leq R\leq 1000$。本题前八个测试点每个测试点 8 分，后四个测试点每个测试点 9 分。

Samples

Input #1

3 4
2x+4=10
-3x+13=10
4x-8=16
1 6
1 8
3 6
4 5

Output #1

Input #2

5 3
5x-2=13
8x+5=45
4x-12=8
-2x+10=4
3x-7=2
1 3
1 5
3 5

Output #2

1
2
2

API Response (JSON)

{
  "problem": {
    "name": "[语言月赛 202311] 方程求解",
    "description": {
      "content": "小 A 有 $n$ 个关于 $x$ 的方程，第 $i$ 个方程形如 $a_ix_i+b_i=c_i$。方程的解 $x$ 均为正整数，例如下面几个方程都是符合要求的方程： ``` 2x+4=10 -3x+13=10 4x-8=16 ``` 其中，第一组方程的解为 $x_1=3$，第二组方程的解为 $x_2=1$，第三组方程的解为 $x_3=6$。 小 A 想要知道，给定 $L,R$，在 $L\\",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3892"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 A 有 $n$ 个关于 $x$ 的方程，第 $i$ 个方程形如 $a_ix_i+b_i=c_i$。方程的解 $x$ 均为正整数，例如下面几个方程都是符合要求的方程：\n\n```\n2x+4=10\n-3x+13=10\n4x-8=16\n```\n\n其中，第一组方程的解为 $x_1=3$，第二组方程的解为 $x_2=1$，第三组方程的解为 $x_3=6$。\n\n小 A 想要知道，给定 $L,R$，在 $L\\...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments