Help your friends
All submissions for this problem are available.
Three software engineers are sitting in CCD , tackling a problem. These engineers have been hired by a bank and they need to solve this problem which is crucial for the efficient functioning of the banking processes. The problem is stated below:
You have to answer K queries. Each query is described by 4 integers: a, b, l, r
You have to find max( gcd(p,q) , such that a ≤ p ≤ b and l ≤ q ≤ r ). p and q are integers.
The first line contains one integer: the number of queries, K.
The second line contains 4 integers: a,b,c,d respectively.
The output should contain K integers , one for each query.
- 1 ≤ K ≤ 6 x 105
- 1 ≤ a ≤ b ≤ 106
- 1 ≤ l ≤ r ≤ 106
- min(r-l, b-a) ≤ 103
Input: 1 40 43 11 13 Output: 6
Taking p = 42 and q = 12 gives us gcd(42,12) = 6. This is the maximum possible, and hence is the answer.
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions