Guest User

2697

a guest
Feb 16th, 2012
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Ruby 1.17 KB | None | 0 0
  1. def gcd(a, b)
  2.   if a==0 then return [b, 0, 1]
  3.   else
  4.     (g, xa, xb) = gcd(b%a, a)
  5.     return [g, xb - (b / a) * xa, xa]
  6.   end
  7. end
  8. def diof_solve(a, b, c)
  9.   if a == 0 and b == 0 then return [c == 0, 0, 0]
  10.   elsif a == 0 then return [c % b == 0, 0, c / b, 0]
  11.   elsif b == 0 then return [c % a == 0, c / a, 0, 0]
  12.   else
  13.     (g, xg, yg) = gcd(a, b)
  14.     return [c % g == 0, xg * c / g, yg * c / g, g]
  15.   end
  16. end
  17. (rx, ry, a, b) = gets().split().map { |i| i.to_i() }
  18. (result, x0, y0, g) = diof_solve(a, b, ry - rx)
  19. if a == 0 then puts max(-y0, -1)
  20. elsif b == 0 then puts max(x0, -1)
  21. else
  22.   kl = -x0 * g / b
  23.   kh = y0 * g / a
  24.   kkl = -2000000000
  25.   kkh = 2000000000
  26.   if -x0 * g % b != 0 then kl += 1 end
  27.   if y0 * g % a != 0 then kh += 1 end
  28.   if b * g > 0 then kkl = [kkl, kl].max()
  29.   else kkh = [kkh, kl].min() end
  30.   if a * g > 0 then kkl = [kkl, kh].max()
  31.   else kkh = [kkh, kh].min() end
  32.   if kkl > kkh then puts -1
  33.   elsif kkl == -2000000000
  34.     puts x0 + kkh * b / g - y0 + kkh * a / g
  35.   elsif kkl == 2000000000
  36.     puts x0 + kkl * b / g - y0 + kkl * a / g
  37.   else
  38.     puts [x0 + kkh * b / g - y0 + kkh * a / g, x0 + kkl * b / g - y0 + kkl * a / g].min()
  39.   end
  40. end
Advertisement
Add Comment
Please, Sign In to add comment