求满足 ax + by = m 的 m 的最小值，m 之后的所有值也满足

原文:https://www . geesforgeks . org/find-最小值-m-满足-ax-m-values-m-还-满足/

给定两个正整数‘a’和‘b’，它们代表方程 ax + by = m 中的系数。找到满足方程中 x 和 y 的任何正整数值的 m 的最小值。在这个最小值之后，方程由 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.

这是 Frobenius 硬币问题的一个变种。在 Frobenius 硬币问题中，我们需要找到不能用两个硬币表示的最大数字。面值为“a”和“b”的硬币的最大金额是 a * b–(a+b)。所以最小的数字，可以用两个硬币来表示，之后的所有数字都可以表示，a * b –( a+b)+1。 一个重要的情况是‘a’和‘b’的 GCD 不为 1。例如，如果‘a’= 4 和‘b’= 6，那么所有可以用两个硬币表示的值都是偶数(或者所有可以对等式进行分层的 m 的值都是偶数)。所以所有不是 2 的倍数的值都不能满足方程。在这种情况下，没有最小值，此后所有值都满足等式。 以下是上述思路的实现:

C++

// C++ program to find the minimum value of m that satisfies
// ax + by = m and all values after m also satisfy
#include<bits/stdc++.h>
using namespace std;

int findMin(int a, int b)
{
    // If GCD is not 1, then there is no such value,
    // else value is obtained using "a*b-a-b+1'
    return (__gcd(a, b) == 1)? a*b-a-b+1 : -1;
}

// Driver code
int main()
{
    int a = 4, b = 7;
    cout << findMin(a, b) << endl;
    return 0;
}

Java 语言(一种计算机语言，尤用于创建网站)

// Java program to find the
// minimum value of m that
// satisfies ax + by = m
// and all values after m
// also satisfy
import java.io.*;

class GFG
{
// Recursive function to
// return gcd of a and b   
static int __gcd(int a, int b)
{

    // Everything divides 0
    if (a == 0 && b == 0)
    return 0;

    // base case
    if (a == b)
        return a;

    // a is greater$
    if (a > b)
        return __gcd(a - b, b);
    return __gcd(a, b - a);
}

static int findMin( int a, int b)
{

    // If GCD is not 1, then
    // there is no such value,
    // else value is obtained
    // using "a*b-a-b+1'
    return (__gcd(a, b) == 1)?
        a * b - a - b + 1 : -1;
}

// Driver code
public static void main (String[] args)
{
    int a = 4;
    int b = 7;
    System.out.println(findMin(a, b));
}
}

// This code is contributed
// by akt_mit

Python 3

# Python3 program to find the minimum
# value of m that satisfies ax + by = m
# and all values after m also satisfy

# Recursive function to return
# gcd of a and b
def __gcd(a, b):

    # Everything divides 0
    if (a == 0 or b == 0):
        return 0;

    # base case
    if (a == b):
        return a;

    # a is greater
    if (a > b):
        return __gcd(a - b, b);
    return __gcd(a, b - a);

def findMin( a, b):

    # If GCD is not 1, then
    # there is no such value,
    # else value is obtained
    # using "a*b-a-b+1'
    if(__gcd(a, b) == 1):
        return (a * b - a - b + 1)
    else:
        return -1

# Driver code
a = 4;
b = 7;
print(findMin(a, b));

# This code is contributed by mits

C

// C# program to find the minimum
// value of m that satisfies 
// ax + by = m and all values
// after m also satisfy
class GFG
{
// Recursive function to
// return gcd of a and b
static int __gcd(int a, int b)
{

    // Everything divides 0
    if (a == 0 && b == 0)
    return 0;

    // base case
    if (a == b)
        return a;

    // a is greater$
    if (a > b)
        return __gcd(a - b, b);
    return __gcd(a, b - a);
}

static int findMin( int a, int b)
{

    // If GCD is not 1, then
    // there is no such value,
    // else value is obtained
    // using "a*b-a-b+1'
    return (__gcd(a, b) == 1)?
           a * b - a - b + 1 : -1;
}

// Driver code
public static void Main()
{
    int a = 4;
    int b = 7;
    System.Console.WriteLine(findMin(a, b));
}
}

// This code is contributed
// by mits

服务器端编程语言（Professional Hypertext Preprocessor 的缩写）

<?php
// PHP program to find the
// minimum value of m that
// satisfies ax + by = m
// and all values after m
// also satisfy

// Recursive function to
// return gcd of a and b
function __gcd($a, $b)
{

    // Everything divides 0
    if ($a == 0 or $b == 0)
    return 0;

    // base case
    if ($a == $b)
        return $a;

    // a is greater$
    if ($a > $b)
        return __gcd($a - $b, $b);
    return __gcd($a, $b - $a);
}

function findMin( $a, $b)
{

    // If GCD is not 1, then
    // there is no such value,
    // else value is obtained
    // using "a*b-a-b+1'
    return (__gcd($a, $b) == 1)?
           $a * $b - $a - $b + 1 : -1;
}

    // Driver code
    $a = 4; $b = 7;
    echo findMin($a, $b) ;

// This code is contributed by anuj_67.
?>

java 描述语言

<script>

    // Javascript program
    // to find the minimum
    // value of m that satisfies 
    // ax + by = m and all values
    // after m also satisfy

    // Recursive function to
    // return gcd of a and b
    function __gcd(a, b)
    {

        // Everything divides 0
        if (a == 0 && b == 0)
            return 0;

        // base case
        if (a == b)
            return a;

        // a is greater$
        if (a > b)
            return __gcd(a - b, b);
        return __gcd(a, b - a);
    }

    function findMin(a, b)
    {

        // If GCD is not 1, then
        // there is no such value,
        // else value is obtained
        // using "a*b-a-b+1'
        return (__gcd(a, b) == 1)?
                a * b - a - b + 1 : -1;
    }

    let a = 4;
    let b = 7;
    document.write(findMin(a, b));

</script>

输出:

18

本文由里沙布·贾恩供稿。如果你喜欢 GeeksforGeeks 并想投稿，你也可以使用contribute.geeksforgeeks.org写一篇文章或者把你的文章邮寄到 contribute@geeksforgeeks.org。看到你的文章出现在极客博客主页上，帮助其他极客。 如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://moonapi.com/news/33723.html