### Problem Link

Statement: Problem F. You can submit solution here.

### Brief statement

We have an Arithmetic Progression $$$P$$$ where the first element is $$$A$$$ and the difference between the consecutive terms is $$$B$$$. So the $$$i^{th}$$$ element of $$$P$$$ is $$$P_i=A+i*B$$$.

Again we have an array $$$a$$$ of $$$K$$$ integers. We say that a number $$$S$$$ can be **expressed** by the array elements if there is a solution of the following equation

Note that all $$$x_i$$$ must need to be **non-negative**.

We also have $$$Q$$$ queries of type $$$(L,R)$$$. For each query we need to find how many numbers $$$P_i$$$ ($$$L \leq i \leq R$$$) can be **expressed** using the elements of the array.

### Constraints

$$$1 \leq K,Q \leq5 0$$$

$$$1 \leq a_i \leq 10^5$$$

$$$0 \leq A,B \leq 10^{15}$$$

$$$1 \leq L \leq R \leq 10^{15}$$$

$$$0 \leq P_R \leq 10^{15}$$$

### My idea

This is actually a Congruence Shortest Path Problem. Using this idea we can express the numbers that can be **expressed** using the array elements as some Arithmetic Progressions. So now we have to find the intersection between two arithmetic progressions and we can find it using CRT.

Let $$$M=\min_{i=1}^{K}{a_i}$$$. Using the above idea I can solve the problem in $$$O(K^2*M+Q*M*log(10^{15}))$$$. But I am consistently getting TLE as the problem has $$$10$$$ test cases.

So here I am asking you to help me by offering a better idea that I can't refuse.

You don't need the $$$log(10^{15})$$$ term while querying.

Hint$$$(A + iB) \mod mina$$$ will be periodic. Therefore for each $$$c \in [0, mina)$$$ you can find the first i for which $$$(A + iB) \equiv c \mod mina$$$ and $$$A + iB \geq L_c$$$ (the least integer with remainder $$$c \mod mina$$$ that has a solution.

Thank You. Got AC using your idea!