Answer range queries about the number of terms from an arithmetic progression that fall inside a given interval.
Arithmetic Progression
You are given an arithmetic progression whose terms grow by a fixed difference. For each query, determine how many terms of the progression lie inside the requested interval.
More concretely, imagine all terms of the progression as a sorted sequence. Each query asks for the count of sequence elements between two bounds, inclusive.
The task is to process multiple queries efficiently.
Input Format
- The first line contains the description of the progression.
- The next line contains an integer , the number of queries.
- Each of the next lines contains two integers describing an interval .
If your version of the problem includes a different exact progression definition, interpret the progression as the one specified in the original statement and answer each interval count query accordingly.
Output Format
For each query, output one integer: the number of progression terms that belong to the interval .
Constraints
- The number of queries can be large.
- Values may be large enough that per query is not suitable.
- Use arithmetic reasoning / prefix-count style computations to answer each query efficiently.
Example 1
Input
1 3 3 1 1 1 7 2 10
Output
1 3 3
Explanation
The progression is 1, 4, 7, 10, ... so the intervals contain 1 term, 3 terms, and 3 terms respectively.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.