75C.md (1553B)
1 Source: https://codeforces.com/problemset/problem/75/C 2 3 C. Modified GCD 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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. 22 23 A common divisor for two positive numbers is a number which both numbers are divisible by. 24 25 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. 26 27 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. 28 29 Input 30 31 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). 32 33 Output 34 35 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. 36 37 Examples 38 39 Input 40 41 ``` 42 9 27 43 3 44 1 5 45 10 11 46 9 11 47 ``` 48 49 Output 50 51 ``` 52 3 53 -1 54 9 55 ```