НОД двух чисел, когда одно из них может быть очень большим

Опубликовано: 20 Января, 2022

Даны два числа 'a' и 'b' такие, что (0 <= a <= 10 ^ 12 и b <= b <10 ^ 250). Найдите НОД двух заданных чисел.
Примеры :

 Ввод: a = 978 
       б = 89798763754892653453379597352537489494736
Выход: 6

Ввод: a = 1221 
       б = 1234567891011121314151617181920212223242526272829
Выход: 3

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Solution : In the given problem, we can see that first number ‘a’ can be handled by long long int data type but second number ‘b’ can not be handled by any int data type. Here we read second number as a string and we will try to make it less than and equal to ‘a’ by taking it’s modulo with ‘a’.
Below is implementation of the above idea. 
 

C++

// C++ program to find GCD of two numbers such that
// the second number can be very large.
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
// function to find gcd of two integer numbers
ll gcd(ll a, ll b)
{
    if (!a)
       return b;
    return gcd(b%a,a);
}
 
// Here "a" is integer and "b" is string.
// The idea is to make the second number (represented
// as b) less than and equal to first number by
// calculating its mod with first integer number
// using basic mathematics
ll reduceB(ll a, char b[])
{
    // Initialize result
    ll mod = 0;
 
    // calculating mod of b with a to make
    // b like 0 <= b < a
    for (int i=0; i<strlen(b); i++)
        mod = (mod*10 + b[i] - "0")%a;
 
    return mod; // return modulo
}
 
// This function returns GCD of "a" and "b"
// where b can be very large and is represented
// as a character array or string
ll gcdLarge(ll a, char b[])
{
    // Reduce "b" (second number) after modulo with a
    ll num = reduceB(a, b);
 
    // gcd of two numbers
    return gcd(a, num);
}
 
// Driver program
int main()
{
    // first number which is integer
    ll a = 1221;
 
    // second number is represented as string because
    // it can not be handled by integer data type
    char b[] = "1234567891011121314151617181920212223242526272829";
    if (a == 0)
        cout << b<<2;
    else
        cout << gcdLarge(a, b);
 
    return 0;
}

Java

// Java program to find
// GCD of two numbers
// such that the second
// number can be very large.
 
class GFG
{
 
    // This function computes
    // the gcd of 2 numbers
    private static int gcd(int reduceNum, int b)
    {
        return b == 0 ?
            reduceNum : gcd(b, reduceNum % b);
    }
 
    // Here "a" is integer and "b"
    // is string. The idea is to make
    // the second number (represented
    // as b) less than and equal to
    // first number by calculating its
    // modulus with first integer
    // number using basic mathematics
    private static int reduceB(int a, String b)
    {
        int result = 0;
        for (int i = 0; i < b.length(); i++)
        {
            result = (result * 10 +
                      b.charAt(i) - "0") % a;
        }
        return result;
    }
 
    private static int gcdLarge(int a, String b)
    {
        // Reduce "b" i.e the second
        // number after modulo with a
        int num = reduceB(a, b);
         
        // Now,use the euclid"s algorithm
        // to find the gcd of the 2 numbers
        return gcd(num, a);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // First Number which
        // is the integer
        int a = 1221;
         
        // Second Number is represented
        // as a string because it cannot
        // be represented as an integer
        // data type
        String b = "19837658191095787329";
        if (a == 0)
            System.out.println(b);
        else
            System.out.println(gcdLarge(a, b));
    }
 
// This code is contributed
// by Tanishq Saluja.
}

Python3

# Python3 program to find GCD of
# two numbers such that the second
# number can be very large.
 
 
# Function to find gcd
# of two integer numbers
def gcd(a, b) :
     
    if (a == 0) :
        return b
         
    return gcd(b % a, a)
 
# Here "a" is integer and "b" is string.
# The idea is to make the second number
# (represented as b) less than and equal
# to first number by calculating its mod
# with first integer number using basic
# mathematics
def reduceB(a, b) :
     
    # Initialize result
    mod = 0
 
    # Calculating mod of b with a
    # to make b like 0 <= b < a
    for i in range(0, len(b)) :
         
        mod = (mod * 10 + ord(b[i])) % a
 
    return mod      # return modulo
 
 
# This function returns GCD of
# "a" and "b" where b can be
# very large and is represented
# as a character array or string
def gcdLarge(a, b) :
     
    # Reduce "b" (second number)
    # after modulo with a
    num = reduceB(a, b)
 
    # gcd of two numbers
    return gcd(a, num)
 
 
# Driver program
 
# First number which is integer
a = 1221
 
# Second number is represented
# as string because it can not
# be handled by integer data type
b = "1234567891011121314151617181920212223242526272829"
if a == 0:
    print(b)
else:
    print(gcdLarge(a, b))
 
 
# This code is contributed by Nikita Tiwari.

C#

// C# program to find GCD of
// two numbers such that the
// second number can be very large.
using System;
 
class GFG
{
// function to find gcd
// of two integer numbers
public long gcd(long a, long b)
{
    if (a == 0)
    return b;
    return gcd(b % a, a);
}
 
// Here "a" is integer and
// "b" is string. The idea
// is to make the second
// number (represented as b)
// less than and equal to
// first number by calculating
// its mod with first integer
// number using basic mathematics
public long reduceB(long a, string b)
{
    // Initialize result
    long mod = 0;
 
    // calculating mod of
    // b with a to make
    // b like 0 <= b < a
    for (int i = 0; i < b.Length; i++)
        mod = (mod * 10 +
              (b[i] - "0")) % a;
 
    return mod;
}
 
// This function returns GCD
// of "a" and "b" where b can
// be very large and is
// represented as a character
// array or string
public long gcdLarge(long a, string b)
{
    // Reduce "b" (second number)
    // after modulo with a
    long num = reduceB(a, b);
 
    // gcd of two numbers
    return gcd(a, num);
}
 
// Driver Code
static void Main()
{
    // first number
    // which is integer
    long a = 1221;
 
    // second number is represented
    // as string because it can not
    // be handled by integer data type
    string b = "1234567891011121314151617181920212223242526272829";
    GFG p = new GFG();
    if (a == 0)
        Console.WriteLine(b);
    else
        Console.WriteLine(p.gcdLarge(a, b));
 
}
}
 
// This code is contributed by mits.

PHP

<?php
// PHP program to find GCD of
// two numbers such that the
// second number can be very large.
 
// function to find gcd of
// two integer numbers
function gcd($a, $b)
{
    if (!$a)
    return $b;
    return gcd($b % $a, $a);
}
 
// Here "a" is integer and "b"
// is string. The idea is to
// make the second number
// (represented as b) less than
// and equal to first number by
// calculating its mod with first
// integer number using basic mathematics
function reduceB($a, $b)
{
    // Initialize result
    $mod = 0;
 
    // calculating mod of b with
    // a to make b like 0 <= b < a
    for ($i = 0; $i < strlen($b); $i++)
        $mod = ($mod * 10 +
                $b[$i] - "0") % $a;
 
    // return modulo
    return $mod;
}
 
// This function returns GCD of
// "a" and "b" where b can be
// very large and is represented
// as a character array or string
function gcdLarge($a, $b)
{
    // Reduce "b" (second number)
    // after modulo with a
    $num = reduceB($a, $b);
 
    // gcd of two numbers
    return gcd($a, $num);
}
 
// Driver Code
 
// first number which is integer
$a = 1221;
 
// second number is represented
// as string because it can not
// be handled by integer data type
$b = "1234567891011121314151617181920212223242526272829";
 
if ($a == 0) {
    echo($b);
}
else {
    echo gcdLarge($a, $b);
}
 
// This code is contributed by nitin mittal.
?>

Javascript

<script>
 
// JavaScript program to find GCD of two numbers such that
// the second number can be very large.
 
// function to find gcd of two integer numbers
function gcd( a, b)
{
    if (!a)
       return b;
    return gcd(b%a,a);
}
 
// Here "a" is integer and "b" is string.
// The idea is to make the second number (represented
// as b) less than and equal to first number by
// calculating its mod with first integer number
// using basic mathematics
function reduceB( a,  b)
{
    // Initialize result
    let mod = 0;
 
    // calculating mod of b with a to make
    // b like 0 <= b < a
    for (let i=0; i<b.length-1; i++)
        mod = (mod*10 + b[i] - "0")%a;
 
    return mod; // return modulo
}
 
// This function returns GCD of "a" and "b"
// where b can be very large and is represented
// as a character array or string
function gcdLarge( a, b)
{
    // Reduce "b" (second number) after modulo with a
    let num = reduceB(a, b);
 
    // gcd of two numbers
    return gcd(a, num);
}
 
// Driver program
  // first number which is integer
    let a = 1221;
 
    // second number is represented as string because
    // it can not be handled by integer data type
    let b = "1234567891011121314151617181920212223242526272829";
    if (a == 0)
        document.write( b);
    else
        document.write(gcdLarge(a, b));
 
// This code contributed by aashish1995
 
</script>

Выход :

 3

Автор статьи - Шашанк Мишра (Гуллу). Эта статья рецензируется командой GeeksforGeeks. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

РЕКОМЕНДУЕМЫЕ СТАТЬИ