丢番图方程是一个多项式方程，通常包含两个或多个未知量，因此只需要积分解。积分解是所有未知变量只取整数值的解。 给定三个整数a、b、c，表示形式为ax+by=c的线性方程。确定方程是否有解，使得x和y都是整数值。 例如：
null
Input : a = 3, b = 6, c = 9Output: PossibleExplanation : The Equation turns out to be, 3x + 6y = 9 one integral solution would be x = 1 , y = 1Input : a = 3, b = 6, c = 8Output : Not PossibleExplanation : o integral values of x and y exists that can satisfy the equation 3x + 6y = 8Input : a = 2, b = 5, c = 1Output : PossibleExplanation : Various integral solutionspossible are, (-2,1) , (3,-1) etc.
解决方案： 对于线性丢番图方程，积分解存在的充要条件是两个变量的系数的GCD将常数项完美分割。换句话说，如果GCD（a，b）除以c，则积分解存在。 因此，确定方程是否有积分解的算法非常简单。
- 找到a和b的GCD
- 检查c%GCD（a，b）=0
- 如果是，则尽可能打印
- 否则无法打印
下面是上述方法的实现。
C++
// C++ program to check for solutions of diophantine // equations #include <bits/stdc++.h> using namespace std; //utility function to find the GCD of two numbers int gcd( int a, int b) { return (a%b == 0)? abs (b) : gcd(b,a%b); } // This function checks if integral solutions are // possible bool isPossible( int a, int b, int c) { return (c%gcd(a,b) == 0); } //driver function int main() { // First example int a = 3, b = 6, c = 9; isPossible(a, b, c)? cout << "Possible" : cout << "Not Possible" ; // Second example a = 3, b = 6, c = 8; isPossible(a, b, c)? cout << "Possible" : cout << "Not Possible" ; // Third example a = 2, b = 5, c = 1; isPossible(a, b, c)? cout << "Possible" : cout << "Not Possible" ; return 0; } |
JAVA
// Java program to check for solutions of // diophantine equations import java.io.*; class GFG { // Utility function to find the GCD // of two numbers static int gcd( int a, int b) { return (a % b == 0 ) ? Math.abs(b) : gcd(b,a%b); } // This function checks if integral // solutions are possible static boolean isPossible( int a, int b, int c) { return (c % gcd(a, b) == 0 ); } // Driver function public static void main (String[] args) { // First example int a = 3 , b = 6 , c = 9 ; if (isPossible(a, b, c)) System.out.println( "Possible" ); else System.out.println( "Not Possible" ); // Second example a = 3 ; b = 6 ; c = 8 ; if (isPossible(a, b, c)) System.out.println( "Possible" ) ; else System.out.println( "Not Possible" ); // Third example a = 2 ; b = 5 ; c = 1 ; if (isPossible(a, b, c)) System.out.println( "Possible" ); else System.out.println( "Not Possible" ); } } // This code is contributed by anuj_67. |
Python3
# Python 3 program to check for solutions # of diophantine equations from math import gcd # This function checks if integral # solutions are possible def isPossible(a, b, c): return (c % gcd(a, b) = = 0 ) # Driver Code if __name__ = = '__main__' : # First example a = 3 b = 6 c = 9 if (isPossible(a, b, c)): print ( "Possible" ) else : print ( "Not Possible" ) # Second example a = 3 b = 6 c = 8 if (isPossible(a, b, c)): print ( "Possible" ) else : print ( "Not Possible" ) # Third example a = 2 b = 5 c = 1 if (isPossible(a, b, c)): print ( "Possible" ) else : print ( "Not Possible" ) # This code is contributed by # Surendra_Gangwar |
C#
// C# program to check for // solutions of diophantine // equations using System; class GFG { // Utility function to find // the GCD of two numbers static int gcd( int a, int b) { return (a % b == 0) ? Math.Abs(b) : gcd(b, a % b); } // This function checks // if integral solutions // are possible static bool isPossible( int a, int b, int c) { return (c % gcd(a, b) == 0); } // Driver Code public static void Main () { // First example int a = 3, b = 6, c = 9; if (isPossible(a, b, c)) Console.WriteLine( "Possible" ); else Console.WriteLine( "Not Possible" ); // Second example a = 3; b = 6; c = 8; if (isPossible(a, b, c)) Console.WriteLine( "Possible" ) ; else Console.WriteLine( "Not Possible" ); // Third example a = 2; b = 5; c = 1; if (isPossible(a, b, c)) Console.WriteLine( "Possible" ); else Console.WriteLine( "Not Possible" ); } } // This code is contributed by anuj_67. |
PHP
<?php // PHP program to check for solutions of // diophantine equations // utility function to find the // GCD of two numbers function gcd( $a , $b ) { return ( $a % $b == 0) ? abs ( $b ) : gcd( $b , $a % $b ); } // This function checks if integral // solutions are possible function isPossible( $a , $b , $c ) { return ( $c % gcd( $a , $b ) == 0); } // Driver Code // First example $a = 3; $b = 6; $c = 9; if (isPossible( $a , $b , $c ) == true) echo "Possible" ; else echo "Not Possible" ; // Second example $a = 3; $b = 6; $c = 8; if (isPossible( $a , $b , $c ) == true) echo "Possible" ; else echo "Not Possible" ; // Third example $a = 2; $b = 5; $c = 1; if (isPossible( $a , $b , $c ) == true) echo "Possible" ; else echo "Not Possible" ; // This code is contributed by ajit.. ?> |
Javascript
<script> // Javascript program to check for solutions of // diophantine equations // Utility function to find the GCD // of two numbers function gcd(a, b) { return (a % b == 0) ? Math.abs(b) : gcd(b,a%b); } // This function checks if integral // solutions are possible function isPossible(a, b, c) { return (c % gcd(a, b) == 0); } // Driver Code // First example let a = 3, b = 6, c = 9; if (isPossible(a, b, c)) document.write( "Possible" + "<br/>" ); else document.write( "Not Possible" + "<br/>" ); // Second example a = 3; b = 6; c = 8; if (isPossible(a, b, c)) document.write( "Possible" + "<br/>" ) ; else document.write( "Not Possible" + "<br/>" ); // Third example a = 2; b = 5; c = 1; if (isPossible(a, b, c)) document.write( "Possible" + "<br/>" ); else document.write( "Not Possible" + "<br/>" ); </script> |
输出：
PossibleNot PossiblePossible
这是怎么回事？ 让‘a’和‘b’的GCD为‘g’。g除以a和b。这意味着g也除以（ax+by）（如果x和y是整数）。这意味着gcd还使用ax+by=c的关系来划分“c”。参考 这 维基链接了解更多详细信息。 本文由 阿什图什·库马尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
