sal2's blog

I need a hint
By sal2, history, 7 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?
»
7 years ago, hide # |
 
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
»
7 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it
hint 1
hint 2
hint 3
→ Reply
  • »
    »
    7 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    one more hint?

    → Reply
    • »
      »
      »
      7 years ago, hide # ^ |
       
      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