Contar elementos comunes en dos arreglos que contengan múltiplos de N y M

Dadas dos arrays tales que la primera array contiene múltiplos de un entero n que son menores o iguales que k y, de manera similar, la segunda array contiene múltiplos de un entero m que son menores o iguales que k.
La tarea es encontrar el número de elementos comunes entre las arrays.
Ejemplos: 
 

Entrada: n=2 m=3 k=9 
Salida: 1  La
primera array sería = [ 2, 4, 6, 8 ] 
La segunda array sería = [ 3, 6, 9 ] 
6 es el único elemento común
Entrada: n= 1 m=2 k=5 
Salida : 2 
 

Enfoque: 
Encuentre el LCM de n y m. Como LCM es el mínimo común múltiplo de n y m, todos los múltiplos de LCM serían comunes en ambas arrays. El número de múltiplos de LCM que son menores o iguales que k sería igual a k/(LCM(m, n)).
Para encontrar el MCM primero calcule el MCD de dos números usando el algoritmo euclidiano y mcm de n, m es n*m/mcd(n, m).
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the above approach
#include <bits/stdc++.h>
 
using namespace std;
 
// Recursive function to find
// gcd using euclidean algorithm
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
 
// Function to find lcm
// of two numbers using gcd
int lcm(int n, int m)
{
    return (n * m) / gcd(n, m);
}
 
// Driver code
int main()
{
    int n = 2, m = 3, k = 5;
 
    cout << k / lcm(n, m) << endl;
 
    return 0;
}

// Java implementation of the above approach
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG
{
 
// Recursive function to find
// gcd using euclidean algorithm
static int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
 
// Function to find lcm
// of two numbers using gcd
static int lcm(int n, int m)
{
    return (n * m) / gcd(n, m);
}
 
// Driver code
public static void main(String[] args)
{
    int n = 2, m = 3, k = 5;
 
    System.out.print( k / lcm(n, m));
}
}
 
// This code is contributed by mohit kumar 29

# Python3 implementation of the above approach
 
# Recursive function to find
# gcd using euclidean algorithm
def gcd(a, b) :
 
    if (a == 0) :
        return b;
         
    return gcd(b % a, a);
 
# Function to find lcm
# of two numbers using gcd
def lcm(n, m) :
 
    return (n * m) // gcd(n, m);
 
 
# Driver code
if __name__ == "__main__" :
 
    n = 2; m = 3; k = 5;
 
    print(k // lcm(n, m));
 
# This code is contributed by AnkitRai01

// C# implementation of the above approach
using System;
     
class GFG
{
 
// Recursive function to find
// gcd using euclidean algorithm
static int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
 
// Function to find lcm
// of two numbers using gcd
static int lcm(int n, int m)
{
    return (n * m) / gcd(n, m);
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 2, m = 3, k = 5;
 
    Console.WriteLine( k / lcm(n, m));
}
}
 
// This code is contributed by Princi Singh

<script>
 
// javascript implementation of the above approach
// Recursive function to find
// gcd using euclidean algorithm
function gcd(a, b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
 
// Function to find lcm
// of two numbers using gcd
function lcm(n, m)
{
    return (n * m) / gcd(n, m);
}
 
// Driver code
 
var n = 2, m = 3, k = 5;
 
document.write( parseInt(k / lcm(n, m)));
 
// This code is contributed by Amit Katiyar
 
</script>

0

Complejidad del tiempo: O(log(min(n,m)))

Espacio auxiliar: O(log(min(n, m)))