All Tracks>Problem
LCM Range Queries
★★★★★

4.1

9 votes
C++, Math, Number Theory, GCD
Problem

You are given Q queries. In each query, you are given two integers X and R,  find the number of pairs of integers (A,B) such that1≤A<B≤R, andLCM(A,A+1,...,B)=X.

 Input format

  • The first line of the input contains a single integer Q — the number of queries.
  • The next Q lines contain two space-separated integers X and R for each query respectively.

Output format
Output Q lines, each line containing a single integer — the answer to the corresponding query.

Constraints

1≤Q≤100002≤X,R≤1016

Sample Input
3
6 3
12 10
20 3
Sample Output
2
3
0
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first query, the segments [1, 3] and [2, 3] satisfy the condition.
In the second query, the segments [1,4], [2, 4] and [3, 4] satisfy the condition.
In the third query, no segments satisfy the condition. Even though the lcm of [4,5] is 20, but the right endpoint 5 is greater than 3, so it is not counted.

Contributers:
Editor Image

?