Блог пользователя sal2

Автор sal2, история, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
hint 1
hint 2
hint 3
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    one more hint?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.