Задача диофантово уравнение c++

13 сентября 2021, 04:10

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

Сложность алгоритма должна быть равна сложности алгоритма Евклида + константа.

Программу-то я реализовал, но вот проблема: не до конца. Не понял, куда в моем коде можно вставить условие, чтобы x был только положительным числом.(При вводе 10 6 8 выводит -1 3, а должно выводить 1 1) Помогите, пожалуйста!

КОД:

#include <iostream>
#include <time.h> 
using namespace std;
// gcd for 2 values
long gcd(long a, long b) {
    while (a != b) {
        if (a > b) {
            long tmp = a;
            a = b;
            b = tmp;
        }
        b = b - a;
    }
    return a;
}
int main()
{
    // values
     int a = 10,
             b = 6,
             c = 8,
             d,x,y;
cout << endl << "equation: a*x + b*y = c" << endl << endl;
cout << "input data: a = " << a << ", b = " << b << ", c = " << c << '.' << endl;
    // main algorithm of the program        
  clock_t the_time = clock();
        d = gcd(a,b);
        if (c%d != 0)
          { cout << "Impossible!" << endl;};
        if (c%d == 0)
          {
                 a/= d;
                 b/= d;
                 c/= d;
                 for (int k=0; k<=a; k++)
                    {
                         if ((c-b*k)%a == 0){
                             y = k;
                             x = (c-(b*k))/a;
                         }
                         else { cout << endl << "Shit happens!" << endl;};
                     };     
            };
    double seconds = double(clock() - the_time) / CLOCKS_PER_SEC;
    // results
    cout << "output data: x = " << x << ", y = " << y << '.' << endl << endl;
    cout << "runtime: " << seconds << " sec." << endl;
    system("pause");
    return 0;
}

Answer 1

(1, 1) - это неправильный ответ, потому что 10*1+6*1=16, а должно получиться 8. Правильный ответ будет (5,-7). Получить такой ответ можно из любого правильного решения (x, y) путём подбора такого числа k, чтобы в решении (x+b*k, y-a*k) было выполнено ваше условие. То есть вам нужно просто решить систему неравенств (если b>0)

x+b*k >= 0     // Условие неотрицательности
x+b*(k-1) < 0  // Условие минимальности

Но это вы должны сделать сами. Рассмотрю только ваш пример. Вы получили (-1, 3), но первое число отрицательное и не подходит под условие. Решаем систему, которая определяет ваше условие:

-1+6*k >= 0
-1+6*(k-1) < 0

Или

k >= 1/6
k < 7/6

Получается, что единственный вариант положить k=1. Значит считаем ответ (-1+6*1, 3-10*1)=(5, -7). (Поправка после комментариев: на самом деле k=1/2 будет правильно, так как НОД(6, 10)=2).

Если же b<0, то вам нужно самостоятельно подумать как поменять знаки в системе.

Далее, ваш алгоритм Евклида реализован плохо. Но это уже другой вопрос.

Answer 2

решение с помощью расширенного алгоритма Евклида на c++

#include <iostream>
#include<cmath>
using namespace std;
long long gcd_ext(long long a,long long b,long long& x,long long& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = gcd_ext(b, a % b, x, y);
    x -= (a / b) * y;
    swap(x, y);
    return d;
}
 
int main(){
long long a,b,c,x,y,d;
cin>>a>>b>>c;
d=gcd_ext(a,b,x,y);
if(c%d==0){
    long long t = c/d*x,t2=b/d;
    if(t==0)cout<<0<<" "<<c/d*y;
    if(t >0)cout<<t+t2*(-(t/t2))<<" "<<c/d*y-a/d*(-(t/t2));
    if(t < 0)cout<<t+t2*(-((t-t2+1)/t2))<<" "<<c/d*y-a/d*((-((t-t2+1)/t2)));
}
else cout<<"Impossible";
return 0;
}

разбирайтесь в расширенном алгоритме Евклида сами. Суть в том что надо найти такое t где с/d * x +b/dt минимальное и неотрицательно. Надо просто решить уравнение a+bx. a = c/dx,b=b/d,x=t. x - минимально и a+bx - неотрицательное