When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

sal2's blog

By sal2, history, 5 years 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

| Write comment?
»
5 years 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)

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

    one more hint?

    • »
      »
      »
      5 years 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.