弗罗贝尼乌斯硬币问题

给出两种面额分别为“X”和“Y”的硬币，找出使用这两种硬币无法获得的最大金额（假设硬币无限供应），然后是此类无法获得的金额的总数，如果不存在此类值，请打印“NA”。

例如：

Input : X=2, Y=5  
Output: Largest amount = 3
        Total count  = 2
We cannot represent 1 and 3 from infinite supply
of given two coins. The largest among these 2 is 3.
We can represent all other amounts for example 13
can be represented 2*4 + 5.

Input : X=5, Y=10
Output: NA
There are infinite number of amounts that cannot
be represented by these two coins.

我们强烈建议您在继续解决方案之前单击此处并进行练习。

一个重要的观察结果是，如果X和Y的GCD不是一，那么给定两个硬币可以形成的所有值都是GCD的倍数。例如，如果X=4，Y=6。那么所有值都是2的倍数。所以，所有不是2的倍数的值，都不能由X和Y形成。因此，存在无穷多个不能由4和6形成的值，我们的答案变成“NA”。

n个硬币的一般问题称为经典福布斯硬币问题。

When the number of coins is two, there is 
explicit formula if GCD is not 1. The formula
is:
  Largest amount A = (X * Y) - (X + Y)
  Total amount = (X -1) * (Y - 1) /2 
 

因此，我们现在可以通过以下步骤轻松回答上述问题：

1. 计算X和Y的GCD
2. 如果GCD为1，则要求的最大金额为（X*Y）-（X+Y），总计数为（X-1）*（Y-1）/2
3. 否则打印“NA”

   下面是一个基于同样的程序。

   C++

   // C++ program to find the largest number that // cannot be formed from given two coins #include <bits/stdc++.h> using namespace std; // Utility function to find gcd int gcd( int a, int b) { int c; while (a != 0) { c = a; a = b%a; b = c; } return b; } // Function to print the desired output void forbenius( int X, int Y) { // Solution doesn't exist // if GCD is not 1 if (gcd(X,Y) != 1) { cout << "NA" ; return ; } // Else apply the formula int A = (X*Y)-(X+Y); int N = (X-1)*(Y-1)/2; cout << "Largest Amount = " << A << endl; cout << "Total Count = " << N << endl; } // Driver Code int main() { int X = 2,Y = 5; forbenius(X,Y); X = 5, Y = 10; cout << endl; forbenius(X,Y); return 0; }

   JAVA

   // Java program to find the largest // number that cannot be formed // from given two coins import java.io.*; class GFG { // Utility function to find gcd static int gcd( int a, int b) { int c; while (a != 0 ) { c = a; a = b % a; b = c; } return b; } // Function to print the // desired output static void forbenius( int X, int Y) { // Solution doesn't exist // if GCD is not 1 if (gcd(X, Y) != 1 ) { System.out.println( "NA" ); return ; } // Else apply the formula int A = (X * Y) - (X + Y); int N = (X - 1 ) * (Y - 1 ) / 2 ; System.out.println( "Largest Amount = " + A ); System.out.println( "Total Count = " + N ); } // Driver Code public static void main(String[] args) { int X = 2 ,Y = 5 ; forbenius(X, Y); X = 5 ; Y = 10 ; System.out.println(); forbenius(X, Y); } } // This code is contributed by Sam007

   Python3

   # Python3 program to find the largest # number that cannot be formed # from given two coins # Utility function to find gcd def gcd(a, b): while (a ! = 0 ): c = a; a = b % a; b = c; return b; # Function to print the desired output def forbenius(X, Y): # Solution doesn't exist # if GCD is not 1 if (gcd(X, Y) ! = 1 ): print ( "NA" ); return ; # Else apply the formula A = (X * Y) - (X + Y); N = (X - 1 ) * (Y - 1 ) / / 2 ; print ( "Largest Amount =" , A); print ( "Total Count =" , N); # Driver Code X = 2 ; Y = 5 ; forbenius(X, Y); X = 5 ; Y = 10 ; print (""); forbenius(X, Y); # This code is contributed by mits

   C#

   // C# program to find the largest //  number that cannot be formed // from given two coins using System; class GFG { // Utility function to find gcd static int gcd( int a, int b) { int c; while (a != 0) { c = a; a = b%a; b = c; } return b; } // Function to print the // desired output static void forbenius( int X, int Y) { // Solution doesn't exist // if GCD is not 1 if (gcd(X,Y) != 1) { Console.WriteLine( "NA" ); return ; } // Else apply the formula int A = (X * Y) - (X + Y); int N = (X - 1) * (Y - 1) / 2; Console.WriteLine( "Largest Amount = " + A ); Console.WriteLine( "Total Count = " + N ); } // Driver Code public static void Main() { int X = 2,Y = 5; forbenius(X,Y); X = 5; Y = 10; Console.WriteLine(); forbenius(X,Y); } } // This code is contributed by Sam007

   PHP

   <?php // php program to find the largest // number that cannot be formed // from given two coins // Utility function to find gcd function gcd( $a , $b ) { $c ; while ( $a != 0) { $c = $a ; $a = $b % $a ; $b = $c ; } return $b ; } // Function to print the desired output function forbenius( $X , $Y ) { // Solution doesn't exist // if GCD is not 1 if (gcd( $X , $Y ) != 1) { echo "NA" ; return ; } // Else apply the formula $A = ( $X * $Y ) - ( $X + $Y ); $N = ( $X - 1) * ( $Y - 1) / 2; echo "Largest Amount = " , $A , "" ; echo "Total Count = " , $N , "" ; } // Driver Code $X = 2; $Y = 5; forbenius( $X , $Y ); $X = 5; $Y = 10; echo "" ; forbenius( $X , $Y ); // This code is contributed by ajit. ?>

   输出：

   Largest Amount = 3
   Total Count = 2
   
   NA
   

   参考资料： https://en.wikipedia.org/wiki/Coin_problem

   本文由 阿什图什·库马尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论