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:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.