معادلات دیوفانتین
Problem
اعداد طبیعی a، b، c داده شده است. اگر معادله \(ax+by=c\) حلولهایی به صورت اعداد صحیح دارد، سپس راه حلی را انتخاب کنید که در آن عدد x کمترین مقدار غیر منفی را دارد و این راه حل را خروجی می کند (دو عدد x و y جدا شده یک فاصله >). اگر راه حلی وجود ندارد، کلمه غیر ممکن را چاپ کنید.
ورودی
سه عدد طبیعی وارد شده است.
حصر
پاسخ مشکل را چاپ کنید.
یادداشت
پیچیدگی الگوریتم باید برابر با پیچیدگی الگوریتم اقلیدسی + یک ثابت باشد.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
1 2 3 |
1 1 |
| 2 |
10 6 8 |
2 -2 |
Запрещенные операторы: gcd