Advertisement
danya11334

Untitled

Feb 20th, 2025
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.30 KB | None | 0 0
  1. import sys
  2. from math import gcd
  3.  
  4. def extended_gcd(a, b):
  5.     """ Расширенный алгоритм Евклида: находит x, y такие, что ax + by = gcd(a, b) """
  6.     if b == 0:
  7.         return 1, 0, a
  8.     y, x, g = extended_gcd(b, a % b)
  9.     return x, y - (a // b) * x, g
  10.  
  11. def solve(n, a, b):
  12.     d = gcd(a, b)
  13.    
  14.     # Проверяем, делится ли n на d
  15.     if n % d != 0:
  16.         return "NO"
  17.  
  18.     # Приводим уравнение к ax + by = 1
  19.     a1, b1, n1 = a // d, b // d, n // d
  20.     x0, y0, _ = extended_gcd(a1, b1)
  21.  
  22.     # Масштабируем базовое решение на n1
  23.     x0 *= n1
  24.     y0 *= n1
  25.  
  26.     # Подбираем k, чтобы x и y стали неотрицательными
  27.     def ceil_div(x, y):
  28.         return x // y if x % y == 0 else x // y + 1
  29.  
  30.     def floor_div(x, y):
  31.         return x // y
  32.  
  33.     k_min = ceil_div(-x0, b1)
  34.     k_max = floor_div(y0, a1)
  35.  
  36.     if k_min > k_max:
  37.         return "NO"
  38.  
  39.     k = k_min  # Берем минимальное k
  40.     x = x0 + k * b1
  41.     y = y0 - k * a1
  42.  
  43.     return f"YES\n{x} {y}"
  44.  
  45. # Чтение входных данных
  46. n = int(input().strip())
  47. a = int(input().strip())
  48. b = int(input().strip())
  49.  
  50. # Вывод результата
  51. print(solve(n, a, b))
  52.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement