LCM Range Queries
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
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.
