### YouKn0wWho's blog

By YouKn0wWho, 5 years ago,

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

$\sum_{i=1}^{K}{x_i*a_i}=S$

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.

• +16

| Write comment?
 » 5 years ago, # | ← Rev. 2 →   +5 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.
•  » » 5 years ago, # ^ |   0 Thank You. Got AC using your idea!