Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import sys
- from math import gcd
- def extended_gcd(a, b):
- """ Расширенный алгоритм Евклида: находит x, y такие, что ax + by = gcd(a, b) """
- if b == 0:
- return 1, 0, a
- y, x, g = extended_gcd(b, a % b)
- return x, y - (a // b) * x, g
- def solve(n, a, b):
- d = gcd(a, b)
- # Проверяем, делится ли n на d
- if n % d != 0:
- return "NO"
- # Приводим уравнение к ax + by = 1
- a1, b1, n1 = a // d, b // d, n // d
- x0, y0, _ = extended_gcd(a1, b1)
- # Масштабируем базовое решение на n1
- x0 *= n1
- y0 *= n1
- # Подбираем k, чтобы x и y стали неотрицательными
- def ceil_div(x, y):
- return x // y if x % y == 0 else x // y + 1
- def floor_div(x, y):
- return x // y
- k_min = ceil_div(-x0, b1)
- k_max = floor_div(y0, a1)
- if k_min > k_max:
- return "NO"
- k = k_min # Берем минимальное k
- x = x0 + k * b1
- y = y0 - k * a1
- return f"YES\n{x} {y}"
- # Чтение входных данных
- n = int(input().strip())
- a = int(input().strip())
- b = int(input().strip())
- # Вывод результата
- print(solve(n, a, b))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement