satillendlim's blog

By satillendlim, history, 6 months ago, In English,

Can anyone give me a hint to solve this problem https://codeforces.com/contest/1152/problem/C please? Thank you

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

try to make gcd as large as possible; gcd(a,b)=gcd(b-a,a)

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
6 months ago, # |
  Vote: I like it +9 Vote: I do not like it
hint 1
hint 2
hint 3
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    one more hint?

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      d is a divisor of a + k, so there is a integer n that a + k = n * d. Therefore, k = n * da. We also want k to be as small as possible, so n should be as small as possible.