satillendlim's blog

By satillendlim, history, 6 months ago, , Can anyone give me a hint to solve this problem https://codeforces.com/contest/1152/problem/C please? Thank you Comments (6)
 » try to make gcd as large as possible; gcd(a,b)=gcd(b-a,a)
•  » » During the contest I too thought that making the gcd as large as possible might be optimal but we have to minimise the lcm which is equal to product of 2 numbers divided by the gcd. How does maximising the gcd ensures minimum lcm. What is the mathematical proof for this
•  » » » yes, this was my question as well, how to guarantee that by maximizing the gcd , the lcm will be minimized and also how to know that gcd(8+k, 12+k) = 4 for example is as maximum as possible when k = 0.
 » hint 1let's suppose $a \leq b$, then $\gcd{(a + k, b + k)} = \gcd{(a + k, b - a)}$ hint 2$\gcd{(a + k, b - a)}$ is a divisor of $b - a$ hint 3for each $d$, divisor of $b - a$, we are trying to find such k that $\gcd{(a + k, b - a)} = d$
•  » » one more hint?
•  » » » d is a divisor of a + k, so there is a integer n that a + k = n * d. Therefore, k = n * d — a. We also want k to be as small as possible, so n should be as small as possible.