1390. The Largest Divisor That Still Fits
For each query print the largest divisor of n that is at most k.
n = 12, k = 5 -> 4 divisors are 1 2 3 4 6 12
n = 12, k = 12 -> 12
n = 12, k = 1 -> 1
An answer always exists, because 1 divides everything and k is at least 1.
## What most people try first
Count down from k and test divisibility. That is O(k) per query, which is
10^12. Counting up from 1 and keeping the last hit is the same cost.
## Divisors come in pairs
Problem 1318 counts divisors with this observation and problem 1334 sums them.
If d divides n then so does n/d, and one member of each pair is at most
sqrt(n). So walking d from 1 to sqrt(n) sees every divisor, as d
itself and as its partner n/d:
d = 1 .. sqrt(n):
if d divides n:
consider d and consider n/d
Both members of the pair have to be considered, not just the small one. For
n = 12, k = 5 the answer 4 is a small-side divisor, while for
n = 12, k = 12 the answer 12 is a large-side one, and a solution that checks
only one side gets one of those wrong.
## Why the largest is found
The walk visits all divisors, so taking the maximum of those not exceeding k
is exactly the answer. There is no need to sort: a running maximum is enough,
because the question asks for one extreme value rather than an ordered list.
A tempting shortcut is to walk d upward and stop at the first n/d that is
at most k, since n/d decreases as d grows. That gives the largest
large-side divisor at most k, which is often but not always the answer:
for n = 36, k = 7 the large side offers 6 at d = 6 while the small side
offers 6 as well, and for n = 12, k = 5 the large side offers 3 while the
answer is 4. So the shortcut needs the small side anyway.
## Overflow
n reaches 10^12, far past a signed 32-bit integer's limit of 2147483647,
and the loop condition d * d <= n reaches 10^12 too. A 32-bit build reports
1 where the truth is 800000, which looks like a legitimate answer. In
JavaScript both quantities stay below 2^53, so plain Number arithmetic is
exact, provided no bitwise operator is used, since those truncate to 32 bits.
## Cost
O(sqrt(n)) per query.
Constraints - `1 ≤ q ≤ 100` - `1 ≤ n ≤ 1000000000000` - `1 ≤ k ≤ 1000000000000`
Input
The first line contains q.
Each of the next q lines contains two integers n and k.
Output
For each query print the largest divisor of n that is at most k, one per line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.