Рубрики

Найдите наименьшие значения x и y, такие что ax — by = 0

Учитывая два значения «a» и «b», которые представляют коэффициенты в «ax — by = 0», найдите наименьшие значения x и y, которые удовлетворяют уравнению. Можно также предположить, что x> 0, y> 0, a> 0 и b> 0.

Input: a = 25, b = 35
Output: x = 7, y = 5

Простое решение — попробовать все возможные значения x и y, начиная с 1, 1, и остановиться, когда уравнение выполнено.

Прямое решение заключается в использовании наименьшего общего множителя (LCM). LCM «a» и «b» представляет наименьшее значение, которое может сделать обе стороны равными. Мы можем найти LCM, используя формулу ниже.

   LCM(a, b) = (a * b) / GCD(a, b) 

Величайший общий делитель (GCD) может быть вычислен с использованием алгоритма Евклида .

C ++

// C ++ программа для поиска наименьших значений x и y, которые
// удовлетворяем "ax - by = 0"
#include <iostream>

using namespace std;

  
// Чтобы найти GCD, используя алгоритм Eculcid

int gcd(int a, int b)

{

    if (b == 0)

        return a;

    return (gcd(b, a % b));

}

  
// Печатает наименьшие значения x и y, которые
// удовлетворяем "ax - by = 0"

void findSmallest(int a, int b)

{

    // Найти LCM

    int lcm = (a * b) / gcd(a, b);

  

    cout << "x = " << lcm / a

         << "\ny = " << lcm / b;

}

  
// Драйвер программы

int main()

{

    int a = 25, b = 35;

    findSmallest(a, b);

    return 0;

}

Джава

// Java-программа для поиска наименьших значений
// x и y, которые удовлетворяют "ax - by = 0"

class GFG {

  

    // Чтобы найти GCD, используя алгоритм Eculcid

    static int gcd(int a, int b)

    {

  

        if (b == 0)

            return a;

        return (gcd(b, a % b));

    }

  

    // Печатает наименьшие значения x и y, которые

    // удовлетворяем "ax - by = 0"

    static void findSmallest(int a, int b)

    {

  

        // Найти LCM

        int lcm = (a * b) / gcd(a, b);

  

        System.out.print("x = " + lcm / a

                         + "\ny = " + lcm / b);

    }

  

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

    public static void main(String[] args)

    {

        int a = 25, b = 35;

        findSmallest(a, b);

    }

}

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

python3

# Программа Python для поиска
# наименьшие значения х и у, которые
# удовлетворить "топор - по = 0"

  
# Чтобы найти GCD, используя алгоритм Eculcid

def gcd(a, b):

    if (b == 0):

        return a

    return(gcd(b, a % b))

  
# Печатает наименьшие значения x и y, которые
# удовлетворить "топор - по = 0"

def findSmallest(a, b):

  

    # Найти LCM

    lcm = (a * b)/gcd(a, b)

    print("x =", lcm / a, "\ny = ", lcm / b)

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

a = 25

b = 35

findSmallest(a, b)

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для поиска самых маленьких
// значения x и y, которые
// удовлетворяем "ax - by = 0"

using System;

  

class GFG {

  

    // Чтобы найти GCD используя

    // алгоритм Экульцида

    static int gcd(int a, int b)

    {

  

        if (b == 0)

            return a;

        return (gcd(b, a % b));

    }

  

    // Печатает наименьшие значения x и

    // у, которые удовлетворяют "ax - by = 0"

    static void findSmallest(int a, int b)

    {

  

        // Найти LCM

        int lcm = (a * b) / gcd(a, b);

  

        Console.Write("x = " + lcm / a + "\ny = " + lcm / b);

    }

  

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

    public static void Main()

    {

        int a = 25, b = 35;

        findSmallest(a, b);

    }

}

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

PHP

<?php
// PHP программа для поиска
// наименьшие значения х
// и у, которые удовлетворяют
// "axe - by = 0"

  
// Чтобы найти GCD используя
// алгоритм Экульцида

function gcd($a, $b)

{

    if ($b == 0)

    return $a;

    return(gcd($b, $a % $b));

}

  
// Печатает наименьшие значения
// из х и у, что
// удовлетворяем "ax - by = 0"

function findSmallest($a, $b)

{

      

    // Найти LCM

    $lcm = ($a * $b) / gcd($a, $b);

  

    echo "x = ", $lcm/$a, "\ny = ", $lcm/$b;

}

  

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

    $a = 25;

    $b = 35;

    findSmallest($a, $b);

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

Выход:

x = 7
y = 5

Приведенный выше код для findSmallest () может быть уменьшен:

Since ax - by = 0,
ax = by, which means x/y = b/a
So we can calculate gcd and directly do as -

Value of x = b / gcd;
Value of y = a / gcd; 

// Печатает наименьшие значения x и y, которые
// удовлетворяем "ax - by = 0"

void findSmallest(int a, int b)

{

    // Найти GCD

    int g = gcd(a, b);

  

    cout << "x = " << b / g

         << "\ny = " << a / g;

}

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

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

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

Найдите наименьшие значения x и y, такие что ax — by = 0

0.00 (0%) 0 votes