Рубрики

Линейные диофантовы уравнения

Диофантово уравнение — это полиномиальное уравнение, обычно с двумя или более неизвестными, так что требуются только интегральные решения. Интегральное решение — это такое решение, при котором все неизвестные переменные принимают только целые значения.

Даны три целых числа a, b, c, представляющих линейное уравнение вида: ax + by = c. Определите, имеет ли уравнение такое решение, чтобы x и y были целыми значениями.

Примеры :

Input : a = 3, b = 6, c = 9
Output: Possible
Explanation : The Equation turns out to be, 
3x + 6y = 9 one integral solution would be 
x = 1 , y = 1

Input : a = 3, b = 6, c = 8
Output : Not Possible
Explanation : o integral values of x and y 
exists that can satisfy the equation 3x + 6y = 8

Input : a = 2, b = 5, c = 1
Output : Possible
Explanation : Various integral solutions
possible are, (-2,1) , (3,-1) etc.

Решение:
Для линейных уравнений диофантовых уравнений интегральные решения существуют тогда и только тогда, когда GCD коэффициентов двух переменных делит постоянный член идеально. Другими словами, интегральное решение существует, если GCD (a, b) делит c.

Таким образом, алгоритм определения наличия интегрального решения уравнения довольно прост.

  • Найти ГКД а и б
  • Проверьте, если c% GCD (a, b) == 0
  • Если да, то напечатайте Возможно
  • Иначе печать невозможна

Ниже приведена реализация вышеуказанного подхода.

C ++

// C ++ программа для проверки растворов диофанта
// уравнения
#include <bits/stdc++.h>

using namespace std;

  
// функция полезности для поиска GCD из двух чисел

int gcd(int a, int b)

{

    return (a%b == 0)? abs(b) : gcd(b,a%b);

}

  
// Эта функция проверяет, являются ли интегральные решения
// возможно

bool isPossible(int a, int b, int c)

{

    return (c%gcd(a,b) == 0);

}

  
// функция драйвера

int main()

{

    // Первый пример

    int a = 3, b = 6, c = 9;

    isPossible(a, b, c)? cout << "Possible\n" :

                        cout << "Not Possible\n";

  

    // Второй пример

    a = 3, b = 6, c = 8;

    isPossible(a, b, c)? cout << "Possible\n" :

                       cout << "Not Possible\n";

  

    // Третий пример

    a = 2, b = 5, c = 1;

    isPossible(a, b, c)? cout << "Possible\n" :

                       cout << "Not Possible\n";

  

    return 0;

}

Джава

// Java-программа для проверки решений
// диофантовы уравнения

import java.io.*;

  

class GFG {

      

    // Сервисная функция для поиска GCD

    // из двух чисел

    static int gcd(int a, int b)

    {

        return (a % b == 0) ? 

                Math.abs(b) : gcd(b,a%b);

    }

      

    // Эта функция проверяет, является ли интеграл

    // возможны решения

    static boolean isPossible(int a,

                            int b, int c)

    {

        return (c % gcd(a, b) == 0);

    }

      

    // Функция драйвера

    public static void main (String[] args)

    {

        // Первый пример

        int a = 3, b = 6, c = 9;

        if(isPossible(a, b, c))

            System.out.println( "Possible" );

        else

            System.out.println( "Not Possible");

      

        // Второй пример

        a = 3; b = 6; c = 8;

        if(isPossible(a, b, c))

            System.out.println( "Possible") ;

        else

            System.out.println( "Not Possible");

      

        // Третий пример

        a = 2; b = 5; c = 1;

        if(isPossible(a, b, c))

            System.out.println( "Possible" );

        else

            System.out.println( "Not Possible");

    }

}

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

python3

# Программа Python 3 для проверки решений
# диофантовых уравнений

from math import gcd

  
# Эта функция проверяет, является ли интеграл
# возможны решения

def isPossible(a, b, c):

    return (c % gcd(a, b) == 0)

  
Код водителя

if __name__ == '__main__':

      

    # Первый пример

    a = 3

    b = 6

    c = 9

    if (isPossible(a, b, c)):

        print("Possible")

    else:

        print("Not Possible")

  

    # Второй пример

    a = 3

    b = 6

    c = 8

    if (isPossible(a, b, c)):

        print("Possible")

    else:

        print("Not Possible")

  

    # Третий пример

    a = 2

    b = 5

    c = 1

    if (isPossible(a, b, c)):

        print("Possible")

    else:

        print("Not Possible")

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

C #

// C # программа для проверки
// растворы диофантина
// уравнения

using System;

  

class GFG 

{

      

    // Сервисная функция для поиска

    // ГКД из двух чисел

    static int gcd(int a, int b)

    {

        return (a % b == 0) ? 

                Math.Abs(b) : 

               gcd(b, a % b);

    }

      

    // Эта функция проверяет

    // если интегральные решения

    // возможны

    static bool isPossible(int a,

                           int b, 

                           int c)

    {

        return (c % gcd(a, b) == 0);

    }

      

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

    public static void Main ()

    {

        // Первый пример

        int a = 3, b = 6, c = 9;

        if(isPossible(a, b, c))

            Console.WriteLine("Possible");

        else

            Console.WriteLine("Not Possible");

      

        // Второй пример

        a = 3; b = 6; c = 8;

        if(isPossible(a, b, c))

            Console.WriteLine("Possible") ;

        else

            Console.WriteLine("Not Possible");

      

        // Третий пример

        a = 2; b = 5; c = 1;

        if(isPossible(a, b, c))

            Console.WriteLine("Possible");

        else

            Console.WriteLine("Not Possible");

    }

}

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

PHP

<?php
// PHP программа для проверки решений
// диофантовы уравнения

  
// функция полезности для поиска
// GCD из двух чисел

function gcd($a, $b)

{

    return ($a % $b == 0) ? 

                  abs($b) : gcd($b, $a % $b);

}

  
// Эта функция проверяет, является ли интеграл
// возможны решения

function isPossible($a, $b, $c)

{

    return ($c % gcd($a, $b) == 0);

}

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

  
// Первый пример

$a = 3;

$b = 6;

$c = 9;

if(isPossible($a, $b, $c) == true)

    echo "Possible\n" ;

else

    echo "Not Possible\n";

  
// Второй пример

$a = 3;

$b = 6;

$c = 8;

  

if(isPossible($a, $b, $c) == true)

    echo "Possible\n" ;

else

    echo "Not Possible\n";

  
// Третий пример

$a = 2;

$b = 5;

$c = 1;

if(isPossible($a, $b, $c) == true)

    echo "Possible\n" ;

else

    echo "Not Possible\n";

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

Выход :

Possible
Not Possible
Possible

Как это работает?
Пусть GCD из «a» и «b» будет «g». г делит а и б. Это означает, что g также делит (ax + на) (если x и y являются целыми числами). Это подразумевает, что gcd также делит 'c', используя отношение ax + by = c. Обратитесь к этой вики-ссылке для более подробной информации.

Эта статья предоставлена Ашутошем Кумаром . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Посмотрите вашу статью на главной странице GeeksforGeeks и помогите другим Geeks. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Линейные диофантовы уравнения

0.00 (0%) 0 votes