Número de GCD distintos sumando el mismo número con dos enteros dados

Dados dos enteros positivos N y M , la tarea es encontrar el número de MCD diferentes que se pueden formar sumando un entero K a N y M , donde K ≥ 0 .

Ejemplos:

Entrada: N = 8, M = 4
Salida: 3
Explicación: Si K = 0, entonces MCD(8, 4) = 4, 
Si K = 1, entonces MCD(9, 5) = 1, 
Si K = 2, entonces MCD(10, 6) = 2

Entrada: N = 7, M = 10
Salida: 2
Explicación: Si K = 0, entonces MCD(7, 10) = 1, 
Si K = 2, entonces MCD(9, 12) = 3

Planteamiento: El problema se puede resolver con base en la siguiente idea matemática:

El valor máximo de GCD formado después de sumar cualquier valor de K será abs(N – M).
Además del resultado anterior, si se forma cualquier otro MCD, será un divisor perfecto de abs(N – M).

Siga los pasos a continuación para implementar la idea anterior:

• Encuentre la diferencia absoluta entre N y M (digamos X ).
• Encuentra el número de divisores únicos de la X.
• Devuelva este valor como la respuesta requerida.

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

#include <bits/stdc++.h>
using namespace std;
 
int distinctGCDs(int N, int M)
{
   
  // hs contains different results
  // of GCD can formed
  set<int> hs;
  int diff = abs(N - M);
 
  // Finding perfect divisor
  // for diff variable
  for (int i = 1; i * i <= diff; i++) {
 
    // If we found any perfect divisor
    // we will add it in our Set
    if (diff % i == 0) {
      hs.insert(i);
      hs.insert(diff / i);
    }
  }
 
  // Returning number of distinct GCD's
  // which can be formed
  return hs.size();
}
 
int main() {
  int N = 8;
  int M = 4;
 
  // Function call
  cout << distinctGCDs(N, M);
  return 0;
}
 
// This code is contributed by satwik4409.

// Java code to implemment the approach
 
import java.util.*;
 
class GFG {
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 8;
        int M = 4;
 
        // Function call
        System.out.println(distinctGCDs(N, M));
    }
 
    // Function to find distinct numebrs
    // of GCD's can formed by adding N
    public static int distinctGCDs(int N, int M)
    {
        // hs contains different results
        // of GCD can formed
        Set<Integer> hs = new HashSet<>();
        int diff = Math.abs(N - M);
 
        // Finding perfect divisor
        // for diff variable
        for (int i = 1; i * i <= diff; i++) {
 
            // If we found any perfect divisor
            // we will add it in our Set
            if (diff % i == 0) {
                hs.add(i);
                hs.add(diff / i);
            }
        }
 
        // Returning number of distinct GCD's
        // which can be formed
        return hs.size();
    }
}

# python3 code to implement the above approach
def distinctGCDs(N, M):
     
    # hs contains different results
    # of GCD can formed
    hs = set()
    diff = abs(N - M)
     
    # Finding perfect divisor
    # for diff variable
    i = 1
     
    while i*i <= diff :
        # If we found any perfect divisor
        # we will add it in our Set
        if diff % i == 0 :
            hs.add(i)
            hs.add(int(diff / i))
        i+=1
         
    # Returning number of distinct GCD's
    # which can be formed
     
    return len(hs)
      
# Driver Code
if __name__ == "__main__" :
     
    N = 8
    M = 4
 
    # Function call
    print(distinctGCDs(N, M))
     
# this code is contributed by aditya942003patil

// C# code to implemment the approach
using System;
using System.Collections.Generic;
 
public class GFG {
 
  // Driver Code
  public static void Main(string[] args)
  {
    int N = 8;
    int M = 4;
 
    // Function call
    Console.WriteLine(distinctGCDs(N, M));
  }
 
  // Function to find distinct numebrs
  // of GCD's can formed by adding N
  public static int distinctGCDs(int N, int M)
  {
    // hs contains different results
    // of GCD can formed
    HashSet<int> hs = new HashSet<int>();
    int diff = Math.Abs(N - M);
 
    // Finding perfect divisor
    // for diff variable
    for (int i = 1; i * i <= diff; i++) {
 
      // If we found any perfect divisor
      // we will add it in our Set
      if (diff % i == 0) {
        hs.Add(i);
        hs.Add(diff / i);
      }
    }
 
    // Returning number of distinct GCD's
    // which can be formed
    return hs.Count;
  }
}
 
// This code is contributed by AnkThon

<script>
    // JavaScript code to implemment the approach
 
    const distinctGCDs = (N, M) => {
 
        // hs contains different results
        // of GCD can formed
        let hs = new Set();
        let diff = Math.abs(N - M);
 
        // Finding perfect divisor
        // for diff variable
        for (let i = 1; i * i <= diff; i++) {
 
            // If we found any perfect divisor
            // we will add it in our Set
            if (diff % i == 0) {
                hs.add(i);
                hs.add(diff / i);
            }
        }
 
        // Returning number of distinct GCD's
        // which can be formed
        return hs.size;
    }
 
    let N = 8;
    let M = 4;
 
    // Function call
    document.write(distinctGCDs(N, M));
 
    // This code is contributed by rakeshsahni
 
</script>

3

Complejidad de tiempo: O(sqrt(abs(N – M)))
Espacio auxiliar: O(sqrt(abs(N – M)))