Máximo GCD de dos números posible al agregarles el mismo valor

Dados dos números A y B , la tarea es encontrar el máximo común divisor (MCD) que se puede obtener sumando un número X tanto a A como a B.

Ejemplos

Entrada: A = 1, B = 5
Salida: 4
Explicación: Sumando X = 15, los números obtenidos son A = 16 y B = 20. Por lo tanto, MCD de A, B es 4.

Entrada: A = 2, B = 23
Salida: 21

Enfoque: Este problema se puede resolver de una manera muy optimizada utilizando las propiedades del algoritmo GCD euclidiano . Siga los pasos a continuación para resolver el problema:

• Si a > b: MCD(a, b)= MCD(a – b, b) . Por lo tanto, MCD(a, b) = MCD(a – b, b ).
• Al sumar x a A, B, mcd(a + x, b + x) = mcd(a – b, b + x). Se puede ver que (a – b) permanece constante.
• Se puede decir con seguridad que el GCD de estos números nunca excederá (a – b) . Dado que (b + x) puede convertirse en un múltiplo de (a – b) sumando un posible valor de x .
• Por lo tanto, se puede concluir que GCD permanece (a – b).

A continuación se muestra la implementación del enfoque anterior. 

// C++ implementation of above approach.
#include <iostream>
using namespace std;
 
// Function to calculate maximum
// gcd of two numbers possible by
// adding same value to both a and b
void maxGcd(int a, int b)
{
    cout << abs(a - b);
}
 
// Driver Code
int main()
{
    // Given Input
    int a = 2231;
    int b = 343;
 
    maxGcd(a, b);
 
    return 0;
}

// Java implementation of above approach.
import java.io.*;
 
class GFG
{
 
  // Function to calculate maximum
  // gcd of two numbers possible by
  // adding same value to both a and b
  static void maxGcd(int a, int b)
  {
    System.out.println(Math.abs(a - b));
  }
 
  // Driver Code
  public static void main (String[] args)
  {
 
    // Given Input
    int a = 2231;
    int b = 343;
 
    maxGcd(a, b);
 
  }
}
 
// This code is contributed by Potta Lokesh

# Python3 program for the above approach
 
# Function to calculate maximum
# gcd of two numbers possible by
# adding same value to both a and b
def maxGcd(a, b):
     
    print(abs(a - b))
 
# Driver code
 
# Given Input
a = 2231
b = 343
 
maxGcd(a, b)
 
# This code is contributed by Parth Manchanda

// C# program for the above approach
using System;
 
class GFG{
 
 // Function to calculate maximum
  // gcd of two numbers possible by
  // adding same value to both a and b
  static void maxGcd(int a, int b)
  {
    Console.Write(Math.Abs(a - b));
  }
 
// Driver Code
static public void Main ()
{
     
     // Given Input
    int a = 2231;
    int b = 343;
 
    maxGcd(a, b);
}
}
 
// This code is contributed by code_hunt.

<script>
       // JavaScript Program for the above approach
 
       // Function to calculate maximum
       // gcd of two numbers possible by
       // adding same value to both a and b
       function maxGcd(a, b) {
           document.write(Math.abs(a - b));
       }
 
       // Driver Code
 
       // Given Input
       let a = 2231;
       let b = 343;
 
       maxGcd(a, b);
 
   // This code is contributed by Potta Lokesh
   </script>

1888

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)