ms_shnits

Решение линейных диофантовых уравнений

Oct 20th, 2021
833
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # решение линейных диофантовых уравнений
  2.  
  3. # вычисление наибольшего общего делителя чисел x, y
  4. gcd = lambda x, y : x if not(y) else y if not(x) else gcd(y, x%y)
  5.  
  6. # нахождение частного решения соотношения Безу ax + by = 1 для взаимно простых a, b
  7. bezout = lambda a, b : bezout(b, a)[::-1] if a < b else (0, 1) if b == 1 else (lambda x, y, k : (x, y - k*x))(*bezout(a%b, b), a//b)
  8.  
  9. # решение диофантова уравнения ax + by = c
  10. # x = u t + v
  11. # y = w t + s
  12. # возвращает результат в виде u, v, w, s или всех нулей, если решений нет
  13. diophantus = lambda a, b, c : (0, 0, 0, 0) if c % gcd(a, b) else diophantus(*map(lambda x : x/gcd(a, b), (a, b, c))) if gcd(a, b) != 1 else (lambda a, b, c, x0, y0 : (b, x0*c, -a, y0*c))(a, b, c, *bezout(a, b))
  14.  
  15. # тесты:
  16. print(gcd(17*3, 17*5))
  17. print(bezout(981, 991), 99*981 - 98*991)
  18. print("x = %d * t + (%d),\ty = %d * t + (%d)" % diophantus(17*3, 17*5, 17*4))
RAW Paste Data