Skip to content

Instantly share code, notes, and snippets.

@thameemk612 thameemk612/4
Created Oct 18, 2018

Embed
What would you like to do?
Find the greatest common divisor d between two integers a and b that is in a given range from low to high (inclusive), i.e. low ≤ d ≤ high. It also is possible that there is no common divisor in the given range.
You will be given the two integers a and b, then n queries. Each query is a range from low to high and you have to answer each query.
Input The first line contains two integers a and b, the two integers as described above (1 ≤ a, b ≤ 109). The second line contains one integer n, the number of queries (1 ≤ n ≤ 104). Then n lines follow, each line contains one query consisting of two integers, low and high (1 ≤ low ≤ high ≤ 109).
Output Print n lines. The i-th of them should contain the result of the i-th query in the input. If there is no common divisor in the given range for any query, you should print -1 as a result for this query.
Input Format
9 27
3
1 5
10 11
9 11
Constraints
(1 ≤ n ≤ 104)
(1 ≤ a, b ≤ 109)
Output Format
3
-1
9
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.