Question

Диофантово уравнение 50 Баллов
Даны натуральные числа a
, b
, c
. Если уравнение ax+by=c
имеет решения в целых числах, то выберите то решение, в котором число x
имеет наименьшее неотрицательное значение, и выведите это решение (два числа x
и y
через один пробел). Если решения не существует, то выведите −1
.

Входные данные

Входные данные — натуральные числа a
, b
и c
. Числа заданы на одной строке через пробел и не превышают 109
.

Выходные данные

Выведите ответ на задачу. C++ Киньте код

Answer 1

#include <iostream>

using namespace std;

int gcdExtended(int a, int b, int &x, int &y) {

   if (b == 0) {

       x = 1;

       y = 0;

       return a;

   }

   int x1, y1;

   int gcd = gcdExtended(b, a % b, x1, y1);

   x = y1;

   y = x1 - (a / b) * y1;

   return gcd;

}

bool findSolution(int a, int b, int c, int &x, int &y) {

   int g = gcdExtended(a, b, x, y);

   if (c % g != 0) {

       return false; // Решения не существует

   }

   int k = c / g;

   x *= k;

   y *= k;

   return true;

}

int main() {

   int a, b, c;

   cin >> a >> b >> c;

   

   int x, y;

   if (findSolution(a, b, c, x, y)) {

       // Проверим, что x >= 0

       while (x < 0) {

           x += b;

           y -= a;

       }

       cout << x << " " << y << endl;

   } else {

       cout << -1 << endl;

   }

   

   return 0;

}