Choice Is Yours

We can rewrite $n$ $mod$ $x = k$ as ${x*p = n - k}$ where $p$ is any arbitrary integer. So, it’s clear that $x$ will be a divisor of $n - k$ which is strictly greater than $k$ and the same goes for $y$. Now to obtain maximum $gcd$ we’ve to take $n - k$ as $y$ and the biggest divisor of $y$ as $x$ $i.e$ ${y = n - k}$, $x =$ biggest divisor of $y$ which is not equal to $y$ and greater than $k$. By doing this we can ensure ${gcd(x, y) = x}$ because $x$ divides both $x$ and $y$ and this is the maximum $gcd$ that we can obtain. Now to find the biggest divisor of $y$, we have to factorize $y$. Let $p$ be the smallest prime factor of $y$ where ${y / p > k}$, then ${x = y / p}$. Note that, prime factorization in ${O( \sqrt y)}$ won’t fit in the time limit. So we’ve to factorize $y$ by only the prime numbers which can be found by Sieve of Eratosthenes. There are a total of $78498$ primes under $10^6$. So, it will easily fit in the limit.

Corner Cases: If $y = 1$ or $y \le k$ then the answer will be $-1$. If $y$ is a prime number and $k = 0$, the answer will be $1$. If $y$ is a prime and $k > 0$ then the answer will be $-1$.