Conteo de múltiplos comunes de dos números en un rango

Dado un rango de L a R y cada mosaico X está pintado de negro y cada mosaico Y está pintado de blanco en ese rango de L a R. Si un mosaico está pintado de blanco y negro, entonces se considera que está pintado de gris. La tarea es encontrar el número de mosaicos que son de color gris en el rango L a R (ambos inclusive). 
Ejemplos: 
 

Input: X = 2, Y = 3, L = 6, R = 18
Output: 3
The grey coloured tiles are numbered 6, 12, 18

Input: X = 1, Y = 4, L = 5, R = 10
Output: 1
The only grey coloured tile is 8.

Enfoque: Ya que todo múltiplo de X es negro y todo múltiplo de Y es blanco. Cualquier mosaico que sea un múltiplo de X e Y sería gris. Los términos que son divisibles por X e Y son los términos que son divisibles por el mcm de X y Y.
Lcm se puede encontrar usando la siguiente fórmula: 
 

lcm = (x*y) / gcd(x, y)

GCD se puede calcular en tiempo de registro utilizando el algoritmo de Euclides . El número de múltiplos de mcm en el rango L a R se puede encontrar usando un truco común de: 
 

count(L, R) = count(R) - count(L-1)

Número de términos divisibles por K menos que N es: 
 

floor(N/K)

A continuación se muestra la implementación para encontrar el número de mosaicos grises:
 

// C++ implementation to find the number of
// grey tiles
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the numbe ro fgrey tiles
int findTileCount(int x, int y, int l, int r)
{
    int lcm = (x * y) / __gcd(x, y);
 
    // Number multiple of lcm less than L
    int countl = (l - 1) / lcm;
 
    // Number of multiples of lcm less than R+1
    int countr = r / lcm;
    return countr - countl;
}
 
// Driver code
int main()
{
    int x = 2, y = 3, l = 6, r = 18;
    cout << findTileCount(x, y, l, r);
    return 0;
}

// Java  implementation to find the
// number of grey tiles
 
import java.io.*;
 
class GFG {
    // Function to count the number
// of grey tiles
static int findTileCount(int x, int y,
                         int l, int r)
{
    int lcm = (x * y) / __gcd(x, y);
 
    // Number multiple of lcm less than L
    int countl = (l - 1) / lcm;
 
    // Number of multiples of
    // lcm less than R+1
    int countr = r / lcm;
    return countr - countl;
}
 
static int __gcd(int a, int b)
{
     
    // Everything divides 0
    if (a == 0)
    return b;
    if (b == 0)
    return a;
 
    // base case
    if (a == b)
        return a;
 
    // a is greater
    if (a > b)
        return __gcd(a - b, b);
         
    return __gcd(a, b - a);
}
 
// Driver code
     
     
    public static void main (String[] args) {
 
    int x = 2, y = 3, l = 6, r = 18;
        System.out.println(findTileCount(x, y, l, r));
}
}
 
// This code is contributed ajit

# Python3 implementation to find the number of
# grey tiles
 
# from math lib import gcd method
from math import gcd
 
# Function to count the numbe of grey tiles
def findTileCount(x, y, l, r) :
 
    lcm = (x * y) // gcd(x, y)
 
    # Number multiple of lcm less than L
    count1 = (l - 1) // lcm
 
    # Number of multiples of lcm less than R+1
    countr = r // lcm
 
    return countr - count1
 
 
 
# Driver code
if __name__ == "__main__" :
 
    x, y, l, r = 2, 3, 6, 18
    print(findTileCount(x, y, l, r))
 
# This code is contributed by
# ANKITRAI1

// C# implementation to find the
// number of grey tiles
using System;
 
class GFG
{
     
// Function to count the number
// of grey tiles
static int findTileCount(int x, int y,
                         int l, int r)
{
    int lcm = (x * y) / __gcd(x, y);
 
    // Number multiple of lcm less than L
    int countl = (l - 1) / lcm;
 
    // Number of multiples of
    // lcm less than R+1
    int countr = r / lcm;
    return countr - countl;
}
 
static int __gcd(int a, int b)
{
     
    // Everything divides 0
    if (a == 0)
    return b;
    if (b == 0)
    return a;
 
    // base case
    if (a == b)
        return a;
 
    // a is greater
    if (a > b)
        return __gcd(a - b, b);
         
    return __gcd(a, b - a);
}
 
// Driver code
public static void Main()
{
    int x = 2, y = 3, l = 6, r = 18;
    Console.Write(findTileCount(x, y, l, r));
}
}
 
// This code is contributed
// by Kirti_Mangal

<?php
// PHP implementation to find the
// number of grey tiles
 
// Function to count the number
// of grey tiles
function findTileCount($x, $y, $l, $r)
{
    $lcm = (int)(($x * $y) / __gcd($x, $y));
 
    // Number multiple of lcm less than L
    $countl = (int)(($l - 1) / $lcm);
 
    // Number of multiples of
    // lcm less than R+1
    $countr = (int)($r / $lcm);
    return $countr - $countl;
}
 
function __gcd($a, $b)
{
     
    // Everything divides 0
    if ($a == 0)
    return $b;
    if ($b == 0)
    return $a;
 
    // base case
    if ($a == $b)
        return $a;
 
    // a is greater
    if ($a > $b)
        return __gcd($a - $b, $b);
         
    return __gcd($a, $b - $a);
}
 
// Driver code
$x = 2; $y = 3; $l = 6; $r = 18;
echo findTileCount($x, $y, $l, $r);
     
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>

<script>
 
// JavaScript implementation to find the
// number of grey tiles
 
// Function to count the number
// of grey tiles
function findTileCount(x,y,l,r)
{
    lcm = parseInt((x * y) / __gcd(x, y));
 
    // Number multiple of lcm less than L
    countl = parseInt((l - 1) / lcm);
 
    // Number of multiples of
    // lcm less than R+1
    countr = parseInt(r / lcm);
    return countr - countl;
}
 
function __gcd(a, b)
{
     
    // Everything divides 0
    if (a == 0)
    return b;
    if (b == 0)
    return a;
 
    // base case
    if (a == b)
        return a;
 
    // a is greater
    if (a > b)
        return __gcd(a - b, b);
         
    return __gcd(a, b - a);
}
 
// Driver code
let x = 2;
let y = 3;
let l = 6;
let r = 18;
document.write(findTileCount(x, y, l, r));
 
// This code is contributed by bobby
 
</script>

3

Complejidad del tiempo: O(log(x*y))