Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def gcd(a, b)
- if a==0 then return [b, 0, 1]
- else
- (g, xa, xb) = gcd(b%a, a)
- return [g, xb - (b / a) * xa, xa]
- end
- end
- def diof_solve(a, b, c)
- if a == 0 and b == 0 then return [c == 0, 0, 0]
- elsif a == 0 then return [c % b == 0, 0, c / b, 0]
- elsif b == 0 then return [c % a == 0, c / a, 0, 0]
- else
- (g, xg, yg) = gcd(a, b)
- return [c % g == 0, xg * c / g, yg * c / g, g]
- end
- end
- (rx, ry, a, b) = gets().split().map { |i| i.to_i() }
- (result, x0, y0, g) = diof_solve(a, b, ry - rx)
- if a == 0 then puts max(-y0, -1)
- elsif b == 0 then puts max(x0, -1)
- else
- kl = -x0 * g / b
- kh = y0 * g / a
- kkl = -2000000000
- kkh = 2000000000
- if -x0 * g % b != 0 then kl += 1 end
- if y0 * g % a != 0 then kh += 1 end
- if b * g > 0 then kkl = [kkl, kl].max()
- else kkh = [kkh, kl].min() end
- if a * g > 0 then kkl = [kkl, kh].max()
- else kkh = [kkh, kh].min() end
- if kkl > kkh then puts -1
- elsif kkl == -2000000000
- puts x0 + kkh * b / g - y0 + kkh * a / g
- elsif kkl == 2000000000
- puts x0 + kkl * b / g - y0 + kkl * a / g
- else
- puts [x0 + kkh * b / g - y0 + kkh * a / g, x0 + kkl * b / g - y0 + kkl * a / g].min()
- end
- end
Advertisement
Add Comment
Please, Sign In to add comment