P9853 [Beginner Contest #17] Solving Equations

Xiao A has $n$ equations about $x$. The $i$-th equation is in the form $a_ix_i+b_i=c_i$. The solutions $x$ are all positive integers. For example, the following equations all meet the requirement: ``` 2x+4=10 -3x+13=10 4x-8=16 ``` Among them, the solution to the first equation is $x_1=3$, the solution to the second equation is $x_2=1$, and the solution to the third equation is $x_3=6$. Xiao A wants to know: given $L,R$, within the range $L\leq x\leq R$, how many positive integers $x$ satisfy that $x$ is a solution to at least one of the equations. To prevent you from tricking him, he will ask you $Q$ times.

The first line contains two positive integers $n,Q$, representing the number of equations Xiao A has and the number of queries he will ask. Starting from the second line, the next $n$ lines each contain a string describing an equation. Starting from line $(n+2)$, the next $Q$ lines each contain two positive integers $L,R$, representing one query: given $L,R$, ask how many positive integers $x$ in the range $L\leq x\leq R$ satisfy that $x$ is a solution to at least one of the equations.

For each query, output one line with one integer, indicating how many positive integers $x$ in the range $L\leq x\leq R$ satisfy that $x$ is a solution to at least one of the equations.

**[Sample Explanation]** For the first sample group, it is the example given in the statement. The solutions of the three equations are $x_1=3,x_2=1,x_3=6$. Then: - For the range $1\leq x\leq 6$, there are $3$ values of $x$ ($x=1,3,6$) that are solutions to at least one equation. - For the range $1\leq x\leq 8$, it is the same as above. - For the range $3\leq x\leq 6$, there are $2$ values of $x$ ($x=3,6$) that are solutions to at least one equation. - For the range $4\leq x\leq 5$, there is no $x$ that is a solution to at least one equation. - Therefore, the outputs are $3,3,2,0$. For the second sample group, the solutions of the five equations are $x_1=3,x_2=5,x_3=5,x_4=3,x_5=3$. Then: - For the range $1\leq x\leq 3$, only $x=3$ is a solution to at least one equation. - For the range $1\leq x\leq 5$, there are $2$ values of $x$ ($x=3,5$) that are solutions to at least one equation. - For the range $3\leq x\leq 5$, there are $2$ values of $x$ ($x=3,5$) that are solutions to at least one equation. - Therefore, the outputs are $1,2,2$. **[Constraints]** The testdata guarantees that $1\leq n,Q\leq 2\times 10^5$. In each equation, $a_i,b_i,c_i$ satisfy $1 \leq |a_i|,|b_i|,|c_i| \leq 10^9$, and the solution $x_i$ of each equation must be a positive integer. In each query, $L,R$ satisfy $1\leq L\leq R\leq 2\times 10^9$. The input size is large, so please pay attention to the efficiency of input and output in your code. Translated by ChatGPT 5