sal2's blog

I need a hint
By sal2, history, 6 years ago, In English

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

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

Comments Comments (4)
| Write comment?
»
6 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)

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

    one more hint?

    → Reply
    • »
      »
      »
      6 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 * d — a. We also want k to be as small as possible, so n should be as small as possible.

      → Reply