Сумма минимальных значений x и y, удовлетворяющих уравнению ax + by = c

Опубликовано: 5 Января, 2022

Для трех целых чисел a , b и c, представляющих линейное уравнение вида ax + by = c , задача состоит в том, чтобы найти решение (x, y) данного уравнения, такое, что (x + y) минимизируется. Если для приведенного выше уравнения не существует решения, выведите «-1» .
Примечание: x и y - неотрицательные целые числа.

Примеры:

Input: a = 2, b = 2, c = 0
Output: 0
Explanation:
The given equation is 2x + 2y = 0.
Therefore, x = 0 and y = 0 is the required solution with minimum value of (x + y).
Input: a = 2, b = 2, c = 1
Output: -1
Explanation:
The given equation is 2x + 2y = 1.
No solution exists for the given equation for positive values of x and y.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: Чтобы решить указанную выше проблему, найдите любое решение, скажем (x, y) данного линейного диофантова уравнения, а затем, соответственно, найдите значение x и минимизируйте сумму.
Ниже приведено решение (x ', y') данного уравнения:

[Tex]y’ = y – k * frac{a}{g} [/Tex]

where g is gcd(a, b) and k is any integer.
[Tex]x’ + y’ = x + y + k*frac{b-a}{g} [/Tex]

Из приведенного выше уравнения мы видим, что:

Если a меньше b, нам нужно выбрать наименьшее возможное значение K.
Иначе, если a больше b, нам нужно выбрать максимально возможное значение K.
Если a = b, все решения будут иметь одинаковую сумму (x + y) .

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ program for the above approach
 #include <bits/stdc++.h>
 using namespace std;
 // Function to find the gcd of a & b
 // by Euclid's method
 // x and y store solution of
 // equation ax + by = g
 int gcd( int a, int b, int * x, int * y)
 {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int x1, y1;
    int store_gcd = gcd(b, a % b,
                        &x1, &y1);
    // Euclidean Algorithm
    *x = y1;
    *y = x1 - y1 * (a / b);
    // store_gcd returns
    // the gcd of a and b
    return store_gcd;
 }
 // Function to find any
 // possible solution
 int possible_solution( int a, int b,
                    int c, int * x0,
                    int * y0, int * g)
 {
    *g = gcd( fabs (a), fabs (b), x0, y0); 
    // Condition if solution
    // does not exists
    if (c % *g) {
        return 0;
    }
    *x0 *= c / *g;
    *y0 *= c / *g;
    // Adjusting the sign
    // of x0 and y0
    if (a < 0)
        *x0 *= -1;
    if (b < 0)
        *y0 *= -1;
    return 1;
 }
 // Function to shift solution
 void shift_solution( int * x, int * y,
                    int a, int b,
                    int shift_var)
 {
    // Shifting to obtain
    // another solution
    *x += shift_var * b;
    *y -= shift_var * a;
 }
 // Function to find minimum
 // value of x and y
 int find_min_sum( int a, int b, int c)
 {
    int x, y, g; 
    // g is the gcd of a and b
    if (!possible_solution(a, b, c,
                        &x, &y, &g))
        return -1; 
    a /= g;
    b /= g;
    // Store sign of a and b
    int sign_a = a > 0 ? +1 : -1;
    int sign_b = b > 0 ? +1 : -1; 
    shift_solution(&x, &y, a, b, -x / b);
    // If x is less than 0, then
    // shift solution
    if (x < 0)
        shift_solution(&x, &y, a, b, sign_b);
    int minx1 = x; 
    shift_solution(&x, &y, a, b, y / a);
    // If y is less than 0, then
    // shift solution
    if (y < 0)
        shift_solution(&x, &y, a, b, -sign_a);
    int minx2 = x; 
    if (minx2 > x)
        swap(minx2, x);
    int minx = max(minx1, minx2); 
    // Find intersection such
    // that both x and y are positive
    if (minx > x)
        return -1; 
    // miny is value of y
    // corresponding to minx
    int miny = (c - a * x) / b; 
    // Returns minimum value of x+y
    return (miny + minx);
 }
 // Driver Code
 int main()
 {
    // Given a, b, and c
    int a = 2, b = 2, c = 0; 
    // Function Call
    cout << find_min_sum(a, b, c)
        << "
" ; 
    return 0;
 }

Джава

 // Java program for the above approach
 import java.lang.*;
 class GFG{
    
public static int x = 0 , y = 0 ,
                 x1 = 0 , y1 = 0 ;
 public static int x0 = 0 , y0 = 0 ,
                   g = 0 ;
 // Function to find the gcd of a & b
 // by Euclid's method
 // x and y store solution of
 // equation ax + by = g
 public static int gcd( int a, int b)
 {
    if (b == 0 )
    {
        x = 1 ;
        y = 0 ;
        return a;
    }
    int store_gcd = gcd(b, a % b); 
    // Euclidean Algorithm
    x = y1;
    y = x1 - y1 * (a / b);
    // store_gcd returns
    // the gcd of a and b
    return store_gcd;
 }
 // Function to find any
 // possible solution
 public static int possible_solution( int a, int b,
                                    int c)
 {
    g = gcd(Math.abs(a), Math.abs(b));
    // Condition if solution
    // does not exists
    if (c % g != 0 )
    {
        return 0 ;
    }
    x0 *= c / g;
    y0 *= c / g;
    // Adjusting the sign
    // of x0 and y0
    if (a < 0 )
        x0 *= - 1 ;
    if (b < 0 )
        y0 *= - 1 ; 
    return 1 ;
 }
 // Function to shift solution
 public static void shift_solution( int a, int b,
                                  int shift_var)
 {
    
    // Shifting to obtain
    // another solution
    x += shift_var * b;
    y -= shift_var * a;
 }
 // Function to find minimum
 // value of x and y
 public static int find_min_sum( int a, int b,
                               int c)
 {
    int x = 0 , y = 0 , g = 0 ; 
    // g is the gcd of a and b
    if (possible_solution(a, b, c) == 0 )
        return - 1 ; 
    if (g != 0 )
    {
        a /= g;
        b /= g;
    }
    // Store sign of a and b
    int sign_a = a > 0 ? + 1 : - 1 ;
    int sign_b = b > 0 ? + 1 : - 1 ; 
    shift_solution(a, b, -x / b);
    // If x is less than 0, then
    // shift solution
    if (x < 0 )
        shift_solution(a, b, sign_b);
    int minx1 = x; 
    shift_solution(a, b, y / a);
    // If y is less than 0, then
    // shift solution
    if (y < 0 )
        shift_solution(a, b, -sign_a);
    int minx2 = x; 
    if (minx2 > x)
    {
        int temp = minx2;
        minx2 = x;
        x = temp;
    }
    int minx = Math.max(minx1, minx2); 
    // Find intersection such
    // that both x and y are positive
    if (minx > x)
        return - 1 ; 
    // miny is value of y
    // corresponding to minx
    int miny = (c - a * x) / b; 
    // Returns minimum value of x+y
    return (miny + minx);
 }
 // Driver Code
 public static void main(String[] args)
 {
    
    // Given a, b, and c
    int a = 2 , b = 2 , c = 0 ; 
    // Function call
    System.out.println(find_min_sum(a, b, c));
 }
 }
 // This code is contributed by grand_master

Python3

 # Python3 program for the
 # above approach
 x, y, x1, y1 = 0 , 0 , 0 , 0
 x0, y0, g = 0 , 0 , 0
 # Function to find the gcd
 # of a & b by Euclid's method
 # x and y store solution of
 # equation ax + by = g
 def gcd(a, b) :
    
    global x, y, x1, y1
    if (b = = 0 ) :
    
        x = 1
        y = 0
        return a
    
    store_gcd = gcd(b, a % b)
    
    # Euclidean Algorithm
    x = y1
    y = x1 - y1 * (a / / b)
    
    # store_gcd returns
    # the gcd of a and b
    return store_gcd
 # Function to find any
 # possible solution
 def possible_solution(a, b, c) :
    
    global x0, y0, g
    g = gcd( abs (a), abs (b))
    
    # Condition if solution
    # does not exists
    if (c % g ! = 0 ) :
    
        return 0
    
    x0 * = c / / g
    y0 * = c / / g
    
    # Adjusting the sign
    # of x0 and y0
    if (a < 0 ) :
        x0 * = - 1
    if (b < 0 ) :
        y0 * = - 1
    return 1
 # Function to shift solution
 def shift_solution(a, b, shift_var) :
    
    global x, y
    # Shifting to obtain
    # another solution
    x + = shift_var * b
    y - = shift_var * a
 # Function to find minimum
 # value of x and y
 def find_min_sum(a, b, c) :
    global x, y, g
    x, y, g = 0 , 0 , 0
    
    # g is the gcd of a and b
    if (possible_solution(a, b, c) = = 0 ) :
        return - 1
    
    if (g ! = 0 ) :
    
        a / / = g
        b / / = g
    
    # Store sign of a and b
    if a > 0 :
        sign_a = 1
    else :
        sign_a = - 1
    
    if b > 0 :
        sign_b = 1
    else :
        sign_b = - 1
    
    shift_solution(a, b, - x / / b)
    
    # If x is less than 0,
    # then shift solution
    if (x < 0 ) :
        shift_solution(a, b, sign_b)
    
    minx1 = x
    
    shift_solution(a, b, y / / a)
    
    # If y is less than 0,
    # then shift solution
    if (y < 0 ) :
        shift_solution(a, b, - sign_a)
    
    minx2 = x
    
    if (minx2 > x) :
    
        temp = minx2
        minx2 = x
        x = temp
    
    minx = max (minx1, minx2)
    
    # Find intersection such
    # that both x and y are positive
    if (minx > x) :
        return - 1
    
    # miny is value of y
    # corresponding to minx
    miny = (c - a * x) / / b
    
    # Returns minimum value
    # of x + y
    return (miny + minx) 
 # Given a, b, and c
 a, b, c = 2 , 2 , 0
 # Function call
 print (find_min_sum(a, b, c))
 # This code is contributed by divyesh072019

C #

 // C# program for the
 // above approach
 using System;
 class GFG{
 public static int x = 0, y = 0,
                  x1 = 0, y1 = 0;
 public static int x0 = 0, y0 = 0,
                  g = 0;
 // Function to find the gcd
 // of a & b by Euclid's method
 // x and y store solution of
 // equation ax + by = g
 public static int gcd( int a, int b)
 {
  if (b == 0)
  {
    x = 1;
    y = 0;
    return a;
  }
  int store_gcd = gcd(b,
                      a % b);
  // Euclidean Algorithm
  x = y1;
  y = x1 - y1 *
      (a / b);
  // store_gcd returns
  // the gcd of a and b
  return store_gcd;
 }
 // Function to find any
 // possible solution
 public static int possible_solution( int a,
                                    int b,
                                    int c)
 {
  g = gcd(Math.Abs(a),

                    
                                            Статьи
                                            Олимпиады по программированию
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИОнлайн-обменники: быстрый и удобный способ конвертации активов в современном мире
17 Апреля, 2024
Лучшие онлайн-курсы по WordPress: рейтинг 2024
29 Марта, 2024
Для кого буду полезны услуги SMS-центра
24 Марта, 2024
Что такое экспертиза исходного кода и как ее проводят?
3 Марта, 2024
Как добавить деньги на счет аккаунта Steam через криптовалюту
20 Февраля, 2024
Заказать докторскую диссертацию на заказ
30 Января, 2024
Купить лайки в ВК: зачем, сколько и где
19 Января, 2024
Как добавить деньги на свой аккаунт в Steam и начать покупать игры и контент
12 Января, 2024

    


        
                    < PROGLER >

                

                    Общее
Контакты
Политика конфиденциальности

                    Обучение
Блог

                

                © progler.ru 2024. Все права защищены.
            

    