codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```