300396: CF75C. Modified GCD

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Modified GCD

题意翻译

给定 $a,b$,每次询问 $a,b$ 在 $[l,r]$ 之间的最大公约数,$q$ 组询问。不存在时输出 $−1$。

题目描述

Well, here is another math class task. In mathematics, GCD is the greatest common divisor, and it's an easy task to calculate the GCD between two positive integers. A common divisor for two positive numbers is a number which both numbers are divisible by. But your teacher wants to give you a harder task, in this task you have to 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 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.

输入输出格式

输入格式


The first line contains two integers $ a $ and $ b $ , the two integers as described above ( $ 1<=a,b<=10^{9} $ ). The second line contains one integer $ n $ , the number of queries ( $ 1<=n<=10^{4} $ ). Then $ n $ lines follow, each line contains one query consisting of two integers, $ low $ and $ high $ ( $ 1<=low<=high<=10^{9} $ ).

输出格式


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.

输入输出样例

输入样例 #1

9 27
3
1 5
10 11
9 11

输出样例 #1

3
-1
9

Input

题意翻译

有 $q$ 组询问,每次询问 $a,b$ 在 $[l,r]$ 之间的最大公约数,如果不存在输出 `-1`

加入题单

上一题 下一题 算法标签: