Рубрики

Найдите минимальное значение m, которое удовлетворяет ax + by = m, и все значения после m также удовлетворяют

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

Примеры:

Input: a = 4, b = 7
Output: 18
Explanation: 18 is the smallest value that can
             can be satisfied by equation 4x + 7y.         
             4*1 + 7*2 = 18

             And after 18 all values are satisifed 
             4*3 + 7*1 = 19
             4*5 + 7*0 = 20
             ... and so on.

Это вариант проблемы монет Фробениуса . В задаче о монетах Фробениуса нам нужно найти наибольшее число, которое нельзя представить двумя монетами. Наибольшее количество монет с номиналами «а» и «b» составляет a * b — (a + b). Таким образом, наименьшее число, такое, что оно может быть представлено с использованием двух монет и всех чисел после того, как оно также может быть представлено, это a * b — (a + b) + 1.

Один важный случай, когда GCD для 'a' и 'b' не равен 1. Например, если 'a' = 4 и 'b' = 6, то все значения, которые могут быть представлены с помощью двух монет, являются четными (или все значения м, которые могут стратифицировать уравнение) являются четными. Таким образом, все значения, НЕ кратные 2, не могут удовлетворять уравнению. В этом случае не существует минимального значения, после которого все значения удовлетворяют уравнению.

Ниже приведена реализация вышеуказанной идеи:

C ++

// C ++ программа для поиска минимального значения m, которое удовлетворяет
// ax + by = m и все значения после m также удовлетворяют
#include<bits/stdc++.h>

using namespace std;

  

int findMin(int a, int b)

{

    // Если GCD не 1, то такого значения нет,

    // иначе значение получается с помощью "a * ba-b + 1 '

    return (__gcd(a, b) == 1)? a*b-a-b+1 : -1;

}

  
// Код драйвера

int main()

{

    int a = 4, b = 7;

    cout << findMin(a, b) << endl;

    return 0;

}

Джава

// Java-программа для поиска
// минимальное значение m, которое
// удовлетворяет ax + by = m
// и все значения после m
// также удовлетворяем

import java.io.*;

  

class GFG

{
// Рекурсивная функция для
// вернуть gcd из a и b

static int __gcd(int a, int b)

{

      

    // Все делит 0

    if (a == 0 && b == 0)

    return 0;

  

    // базовый вариант

    if (a == b)

        return a;

  

    // а больше $

    if (a > b)

        return __gcd(a - b, b);

    return __gcd(a, b - a);

}

  

static int findMin( int a, int b)

{

      

    // Если GCD не 1, то

    // такого значения нет,

    // иначе значение получено

    // используя "a * ba-b + 1 '

    return (__gcd(a, b) == 1)? 

        a * b - a - b + 1 : -1;

}

  
// Код драйвера

public static void main (String[] args) 

{

    int a = 4

    int b = 7;

    System.out.println(findMin(a, b));

}
}

  
// Этот код добавлен
// от akt_mit

python3

# Python3 программа для поиска минимума
# значение m, удовлетворяющее ax + by = m
# и все значения после m также удовлетворяют

  
# Рекурсивная функция для возврата
# gcd a и b

def __gcd(a, b):

      

    # Все делит 0

    if (a == 0 or b == 0):

        return 0;

  

    # базовый вариант

    if (a == b):

        return a;

  

    # больше

    if (a > b):

        return __gcd(a - b, b);

    return __gcd(a, b - a);

  

def findMin( a, b):

      

    # Если GCD не 1, то

    # нет такого значения,

    # еще значение получено

    # используя "a * ba-b + 1 '

    if(__gcd(a, b) == 1):

        return (a * b - a - b + 1

    else:

        return -1

  
# Код драйвера

a = 4

b = 7;

print(findMin(a, b));

      
# Этот код предоставлен mits

C #

// C # программа для поиска минимума
// значение m, удовлетворяющее
// ax + by = m и все значения
// после m также удовлетворяем

class GFG

{
// Рекурсивная функция для
// вернуть gcd из a и b

static int __gcd(int a, int b)

{

      

    // Все делит 0

    if (a == 0 && b == 0)

    return 0;

  

    // базовый вариант

    if (a == b)

        return a;

  

    // а больше $

    if (a > b)

        return __gcd(a - b, b);

    return __gcd(a, b - a);

}

  

static int findMin( int a, int b)

{

      

    // Если GCD не 1, то

    // такого значения нет,

    // иначе значение получено

    // используя "a * ba-b + 1 '

    return (__gcd(a, b) == 1)? 

           a * b - a - b + 1 : -1;

}

  
// Код драйвера

public static void Main() 

{

    int a = 4; 

    int b = 7;

    System.Console.WriteLine(findMin(a, b));

}
}

  
// Этот код добавлен
// по миц

PHP

<?php
// PHP программа для поиска
// минимальное значение m, которое
// удовлетворяет ax + by = m
// и все значения после m
// также удовлетворяем

  
// Рекурсивная функция для
// вернуть gcd из a и b

function __gcd($a, $b)

{

      

    // Все делит 0

    if ($a == 0 or $b == 0)

    return 0;

  

    // базовый вариант

    if ($a == $b)

        return $a;

  

    // а больше $

    if ($a > $b)

        return __gcd($a - $b, $b);

    return __gcd($a, $b - $a);

}

  

function findMin( $a, $b)

{

      

    // Если GCD не 1, то

    // такого значения нет,

    // иначе значение получено

    // используя "a * ba-b + 1 '

    return (__gcd($a, $b) == 1)? 

           $a * $b - $a - $b + 1 : -1;

}

  

    // Код драйвера

    $a = 4; $b = 7;

    echo findMin($a, $b) ;

      
// Этот код предоставлен anuj_67.
?>


Выход:

18

Эта статья предоставлена Rishabh Jain . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найдите минимальное значение m, которое удовлетворяет ax + by = m, и все значения после m также удовлетворяют

0.00 (0%) 0 votes