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;

}

Answer 2

Для решения данной задачи можно воспользоваться расширенным алгоритмом Евклида для нахождения НОД (наибольшего общего делителя) чисел a и b. Если НОД(a, b) делит c, то уравнение ax + by = c имеет решение в целых числах, и мы можем найти такое решение.

Вот C++ код для решения этой задачи:

cppCopy code
#include <iostream>

using namespace std;

// Расширенный алгоритм Евклида для нахождения НОД и коэффициентов x и y
int extendedEuclidean(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

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

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

    return gcd;
}

int main() {
    int a, b, c;
    cin >> a >> b >> c;

    int x, y;
    int gcd = extendedEuclidean(a, b, x, y);

    if (c % gcd != 0) {
        cout << -1 << endl;
    } else {
        // Находим решение уравнения ax + by = c
        x *= c / gcd;
        y *= c / gcd;
        cout << x << " " << y << endl;
    }

    return 0;
}

Этот код сначала находит НОД(a, b) и коэффициенты x и y с помощью расширенного алгоритма Евклида, затем проверяет, делится ли c на НОД(a, b). Если да, то находит решение уравнения и выводит его, иначе выводит -1.