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

# | User | Rating |
---|---|---|

1 | tourist | 3698 |

2 | Petr | 3381 |

3 | mnbvmar | 3379 |

4 | Benq | 3339 |

5 | wxhtxdy | 3329 |

6 | LHiC | 3303 |

7 | ecnerwala | 3300 |

8 | sunset | 3278 |

9 | V--o_o--V | 3275 |

10 | Um_nik | 3240 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 187 |

2 | Errichto | 181 |

3 | rng_58 | 162 |

4 | PikMike | 159 |

5 | Vovuh | 157 |

6 | Petr | 156 |

7 | 300iq | 151 |

8 | majk | 148 |

8 | Um_nik | 148 |

8 | Ashishgup | 148 |

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

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/19/2019 16:50:22 (e2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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?

is a divisor ofd+a, so there is a integerkthatn+a=k*n. Therefore,d=k*n—d. We also wantato be as small as possible, sokshould be as small as possible.n