Problem about GCD
Contest: Educational Codeforces Round 173 (Rated for Div. 2)
Difficulty rating: 1800
Tags: brute force, flows, math, number theory

Given three integers $$$l$$$, $$$r$$$, and $$$G$$$, find two integers $$$A$$$ and $$$B$$$ ($$$l \le A \le B \le r$$$) such that their greatest common divisor (GCD) equals $$$G$$$ and the distance $$$|A - B|$$$ is maximized.

If there are multiple such pairs, choose the one where $$$A$$$ is minimized. If no such pairs exist, output "-1 -1".

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases. Then, $$$t$$$ test cases follow.

Each test case consists of a single line containing three integers $$$l, r, G$$$ ($$$1 \le l \le r \le 10^{18}$$$; $$$1 \le G \le 10^{18}$$$) — the range boundaries and the required GCD.

Output format:
For each test case, output two integers $$$A$$$ and $$$B$$$ — the solution to the problem, or "-1 -1" if no such pair exists.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
4
4 8 2
4 8 3
4 8 4
5 7 6

Example output:
4 6
-1 -1
4 8
6 6

Editorial:
First, let's try to solve this problem with $$$G=1$$$. We can check the pair $$$(l, r)$$$. If its greatest common divisor is not $$$1$$$, then we should check $$$(l, r-1)$$$ and $$$(l+1, r)$$$, i. e. the pairs on the distance $$$(r-l-1)$$$. If these don't work, we can check $$$(l, r-2)$$$, $$$(l+1, r-1)$$$ and $$$(l+2, r)$$$, and so on, and the answer will be located fast enough (more about that in the third paragraph of the editorial). So, we get a solution in $$$O(K^2 \log A)$$$ per test case, where $$$A$$$ is the bound on the integers on the input, and $$$K$$$ is the decrease in distance we had to make to find this pair (i. e. if the answer has distance $$$|A-B|$$$, then $$$K = |r - l| - |A - B|$$$).
What to do if $$$G \ne 1$$$? Almost the same, but first, we need to ensure that the first pair we try has both integers divisible by $$$G$$$. So, if $$$l \bmod G \ne 0$$$, let's shift it to the next closest integer which is divisible by $$$G$$$; and if $$$r \bmod G \ne 0$$$, let's subtract $$$r \bmod G$$$ from $$$r$$$ to make it divisible. Then, we make the same process, but instead of trying pairs like $$$(l, r-1)$$$, $$$(l+1, r)$$$, $$$(l, r-2)$$$ and so on, we try $$$(l, r-G)$$$, $$$(l+G, r)$$$, $$$(l, r - 2G)$$$, and so on.
Okay, now let's talk about why this works fast, i. e. why this $$$K$$$ in the complexity formula is not that big. All the following paragraphs will assume $$$G=1$$$, but we can use the same reasoning with $$$G>1$$$ if we divide everything by $$$G$$$.
Intuitively, we can think about it in terms of prime gaps: as soon as $$$r-K$$$ becomes a prime number, we get our result. Average gap between two primes is about $$$ln A$$$, but there can be pretty big gaps, more than $$$1000$$$. If you're bold and brave, you can stop here and submit, but let's find a better bound.
Instead of thinking about the gap between two primes, let's think about the gap between two numbers which are coprime with $$$l$$$. Let's assume that $$$l$$$ is the product of several first prime numbers (if it is not, integers which are coprime with $$$l$$$ will appear even more often). $$$\frac{1}{2}$$$ of all integers are not divisible by $$$2$$$; $$$\frac{2}{3}$$$ of them are not divisible by $$$3$$$; $$$\frac{4}{5}$$$ of them are not divisible by $$$5$$$, and so on. If we repeat this process until the product of primes we considered becomes too large, we can get that, on average, $$$1$$$ in $$$7$$$ or $$$8$$$ integers is coprime with $$$l$$$. This is a better bound, but it still uses "average" gaps. However, this should be enough to try to submit the solution.
Okay, now let's show a rigorous proof (which you really shouldn't need during the contest) of some reasonable bound. We can prove that if you consider all possible pairs of integers from intervals $$$[l, l+30)$$$ and $$$(r-30, r]$$$, you will find at least one coprime pair.
There are $$$30$$$ integers in each interval, so there are $$$900$$$ pairs to consider. Suppose in some of them, both integers are divisible by $$$2$$$. There will be at most $$$225$$$ such pairs, so we are left with $$$675$$$ pairs.
Suppose in some of the remaining pairs, both integers are divisible by $$$3$$$. There will be at most $$$10$$$ integers divisible by $$$3$$$ in each segment, so at most $$$100$$$ pairs. We are left with $$$575$$$ pairs.
Suppose in some of the remaining pairs, both integers are divisible by $$$5$$$. There will be at most $$$6$$$ integers divisible by $$$5$$$ in each segment, so at most $$$36$$$ pairs. We are left with $$$539$$$ pairs.
If we repeat this until some prime number like $$$37$$$, we will still have to "fix" more than $$$450$$$ pairs, so at least one number has $$$15$$$ or more pairs to "fix". This should mean that it is divisible by at least $$$15$$$ primes which are greater than $$$37$$$, and it means it's greater than $$$10^{18}$$$. So, in every pair of intervals $$$[l, l+30)$$$ and $$$(r-30, r]$$$ such that the numbers are not greater than $$$10^{18}$$$, there will be at least one coprime pair, and this proves that $$$K \le 60$$$. In practice, it is much lower since, in our proof, we didn't consider the fact that a lot of pairs will have more than $$$1$$$ prime which they are divisible by; if we take this into account (or repeat the same process until primes become much greater), we can prove tighter bounds, for example, $$$K = 40$$$.