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.