#1630. [语言月赛 202311] 方程求解

[语言月赛 202311] 方程求解

题目描述

小 A 有 nn 个关于 xx 的方程,第 ii 个方程形如 aixi+bi=cia_ix_i+b_i=c_i。方程的解 xx 均为正整数,例如下面几个方程都是符合要求的方程:

2x+4=10
-3x+13=10
4x-8=16

其中,第一组方程的解为 x1=3x_1=3,第二组方程的解为 x2=1x_2=1,第三组方程的解为 x3=6x_3=6。

小 A 想要知道,给定 L,RL,R,在 L≤x≤RL\leq x\leq R 的范围内,有多少个正整数 xx 满足 xx 是其中至少一个方程的解。为了防止你欺骗他,他会询问你 QQ 次。

输入格式

第一行输入两个正整数 n,Qn,Q,分别表示小 A 有的方程数,以及小 A 想要向你询问的次数。

第二行开始,往下 nn 行,每行一个字符串,描述一个方程。

第 (n+2)(n+2) 行开始,往下 QQ 行,每行两个正整数 L,RL,R,表示一次询问,即给定 L,RL,R,询问在 L≤x≤RL\leq x\leq R 的范围内,有多少个正整数 xx 满足 xx 是其中至少一个方程的解。

输出格式

对于每次询问,输出一行一个整数,表示有多少个在 L≤x≤RL\leq x\leq R 的范围内的正整数 xx,满足 xx 是其中至少一个方程的解。

样例

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

题目来源:洛谷 B3892