N-ésimo número en un conjunto de múltiplos de A, B o C

Dados cuatro enteros N , A , B y C . La tarea es imprimir el ^número N en el conjunto que contiene los múltiplos de A , B o C . 
Ejemplos: 
 

Entrada: A = 2, B = 3, C = 5, N = 8 
Salida: 10 
2, 3, 4, 5, 6, 8, 9, 10 , 12, 14, …
Entrada: A = 2, B = 3 , C = 5, N = 100 
Salida: 136 
 

Enfoque ingenuo: Comience a atravesar desde 1 hasta que encontremos el N ^-ésimo elemento que es divisible por A , B o C .
Enfoque eficiente: dado un número, podemos encontrar el recuento de los divisores de A , B o C . Ahora, la búsqueda binaria se puede usar para encontrar el N número ^divisible por A , B o C .
Entonces, si el número es num entonces 
cuenta = (núm/A) + (núm/B) + (núm/C) – (núm/mcm(A, B)) – (núm/mcm(C, B)) – (núm/mcm(A, C) )) – (num/lcm(A, B, C))
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to find nth term
// divisible by a, b or c
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return
// gcd of a and b
int gcd(int a, int b)
{
    if (a == 0)
        return b;
 
    return gcd(b % a, a);
}
 
long gcd_ab, gcd_bc, gcd_ac, lcm_abc, lcm_ab, lcm_bc, lcm_ac;
 
void preCal(long a, long b, long c) {
    gcd_ab = gcd(a, b); // GCD of a, b
    gcd_bc = gcd(c, b); // GCD of b, c
    gcd_ac = gcd(a, c); // GCD of a, c
    lcm_ab = ((a * b) / gcd_ab); // LCM of a, b
    lcm_bc = ((c * b) / gcd_bc); // LCM of b, c
    lcm_ac = ((a * c) / gcd_ac); // LCM of a, c
    lcm_abc = (lcm_ab * c) / gcd(lcm_ab, c);  // LCM of a, b, c
}
 
// Function to return the count of integers
// from the range [1, num] which are
// divisible by either a, b or c
long divTermCount(long a, long b, long c, long num)
{
    // Calculate the number of terms divisible by a, b
    // and c then remove the terms which are divisible
    // by both (a, b) or (b, c) or (c, a) and then
    // add the numbers which are divisible by a, b and c
    return ((num / a) + (num / b) + (num / c)
            - (num / lcm_ab)
            - (num / lcm_bc)
            - (num / lcm_ac)
            + (num / lcm_abc));
}
 
// Function for binary search to find the
// nth term divisible by a, b or c
int findNthTerm(int a, int b, int c, long n)
{
    // Set low to (gcd(a, b, c) * n) and high to (max(a, b, c) * n)
      // (gcd(a, b, c) * n) is lowest possible value till index 'n'
      // (max(a, b, c) * n) is highest possible value till index 'n'
    preCal(a, b, c);
    long low = 1, high, mid;
    high = max(a, max(b, c)) * n;
    low = gcd(a, gcd_bc) * n;
 
    while (low < high) {
        mid = low + (high - low) / 2;
 
        // If the current term is less than
        // n then we need to increase low
        // to mid + 1
        if (divTermCount(a, b, c, mid) < n)
            low = mid + 1;
 
        // If current term is greater than equal to
        // n then high = mid
        else
            high = mid;
    }
 
    return low;
}
 
// Driver code
int main()
{
    long a = 2, b = 3, c = 5, n = 100;
 
    cout << findNthTerm(a, b, c, n);
 
    return 0;
}
 
// This code was improved by sharad_jain

// Java program to find nth term
// divisible by a, b or c
class GFG
{
      static long gcd_ab, gcd_bc, gcd_ac, lcm_abc, lcm_ab, lcm_bc, lcm_ac;
 
    // Function to return
    // gcd of a and b
    static long gcd(long a, long b)
    {
        if (a == 0)
        {
            return b;
        }
        return gcd(b % a, a);
    }
 
    static void preCal(long a, long b, long c) {
        gcd_ab = gcd(a, b); // GCD of a, b
        gcd_bc = gcd(c, b); // GCD of b, c
        gcd_ac = gcd(a, c); // GCD of a, c
        lcm_ab = ((a * b) / gcd_ab); // LCM of a, b
        lcm_bc = ((c * b) / gcd_bc); // LCM of b, c
        lcm_ac = ((a * c) / gcd_ac); // LCM of a, c
        lcm_abc = (lcm_ab * c) / gcd(lcm_ab, c);  // LCM of a, b, c
    }
 
    // Function to return the count of integers
    // from the range [1, num] which are
    // divisible by either a, b or c
    static long divTermCount(long a, long b,
                             long c, long num)
    {
        // Calculate the number of terms divisible by a, b
        // and c then remove the terms which are divisible
        // by both (a, b) or (b, c) or (c, a) and then
        // add the numbers which are divisible by a, b and c
        return ((num / a) + (num / b) + (num / c)
                - (num / lcm_ab)
                - (num / lcm_bc)
                - (num / lcm_ac)
                + (num / lcm_abc));
    }
 
    // Function for binary search to find the
    // nth term divisible by a, b or c
    static long findNthTerm(int a, int b, int c, long n)
    {
        // Set low to (gcd(a, b, c) * n) and high to (max(a, b, c) * n)
        // (gcd(a, b, c) * n) is lowest possible value till index 'n'
        // (max(a, b, c) * n) is highest possible value till index 'n'
        preCal(a, b, c);
        long low = 1, high, mid;
        high = a > b ? (a > c ? a : c) : (b > c ? b : c);
          high = high * n;
        low = gcd(a, gcd_bc) * n;
 
        while (low < high)
        {
            mid = low + (high - low) / 2;
 
            // If the current term is less than
            // n then we need to increase low
            // to mid + 1
            if (divTermCount(a, b, c, mid) < n)
            {
                low = mid + 1;
            }
             
            // If current term is greater than equal to
            // n then high = mid
            else
            {
                high = mid;
            }
        }
        return low;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int a = 2, b = 3, c = 5, n = 100;
 
        System.out.println(findNthTerm(a, b, c, n));
    }
}
 
// This code is contributed by 29AjayKumar
// This code was improved by sharad_jain

# Python3 program to find nth term
# divisible by a, b or c
import sys
 
# Function to return gcd of a and b
def gcd(a, b):
 
    if (a == 0):
        return b;
 
    return gcd(b % a, a);
   
gcd_ab = 1; gcd_bc = 1; gcd_ac = 1; gcd_abc = 1;
 
def preCal(a, b, c):
    gcd_ab = gcd(a, b);  # GCD of a, b
    gcd_bc = gcd(c, b);  # GCD of b, c
    gcd_ac = gcd(a, c);  # GCD of a, c
    gcd_abc = gcd(((a*b)/gcd_ab), c);  # GCD of a, b, c
 
# Function to return the count of integers
# from the range [1, num] which are
# divisible by either a, b or c
def divTermCount(a, b, c, num):
     
    # Calculate the number of terms divisible by a, b
    # and c then remove the terms which are divisible
    # by both (a, b) or (b, c) or (c, a) and then
    # add the numbers which are divisible by a, b and c
    return ((num / a) + (num / b) + (num / c)
            - (num / ((a * b) / gcd_ab))
            - (num / ((c * b) / gcd_bc))
            - (num / ((a * c) / gcd_ac))
            + (num / ((((a*b)/gcd_ab)* c) / gcd_abc)));
 
# Function for binary search to find the
# nth term divisible by a, b or c
def findNthTerm(a, b, c, n):
 
    # Set low to (gcd(a, b, c) * n) and high to (max(a, b, c) * n)
      # (gcd(a, b, c) * n) is lowest possible value till index 'n'
      # (max(a, b, c) * n) is highest possible value till index 'n'
    preCal(a, b, c);
    mid = 0;
    high = max(a, max(b, c)) * n;
    low = gcd_abc * n;
 
    while (low < high):
        mid = low + (high - low) / 2;
 
        # If the current term is less than
        # n then we need to increase low
        # to mid + 1
        if (divTermCount(a, b, c, mid) < n):
            low = mid + 1;
 
        # If current term is greater than equal to
        # n then high = mid
        else:
            high = mid;
     
    return int(low);
 
# Driver code
a = 2; b = 3; c = 5; n = 100;
 
print(findNthTerm(a, b, c, n));
 
# This code is contributed by 29AjayKumar
# This code was improved by sharad_jain

// C# program to find nth term
// divisible by a, b or c
using System;
 
class GFG
{
      static long gcd_ab, gcd_bc, gcd_ac, lcm_abc, lcm_ab, lcm_bc, lcm_ac;
 
    // Function to return
    // gcd of a and b
    static long gcd(long a, long b)
    {
        if (a == 0)
        {
            return b;
        }
        return gcd(b % a, a);
    }
 
    static void preCal(long a, long b, long c) {
        gcd_ab = gcd(a, b); // GCD of a, b
        gcd_bc = gcd(c, b); // GCD of b, c
        gcd_ac = gcd(a, c); // GCD of a, c
        lcm_ab = ((a * b) / gcd_ab); // LCM of a, b
        lcm_bc = ((c * b) / gcd_bc); // LCM of b, c
        lcm_ac = ((a * c) / gcd_ac); // LCM of a, c
        lcm_abc = (lcm_ab * c) / gcd(lcm_ab, c);  // LCM of a, b, c
    }
 
    // Function to return the count of integers
    // from the range [1, num] which are
    // divisible by either a, b or c
    static long divTermCount(long a, long b,
                             long c, long num)
    {
        // Calculate the number of terms divisible by a, b
        // and c then remove the terms which are divisible
        // by both (a, b) or (b, c) or (c, a) and then
        // add the numbers which are divisible by a, b and c
        return ((num / a) + (num / b) + (num / c)
                - (num / lcm_ab)
                - (num / lcm_bc)
                - (num / lcm_ac)
                + (num / lcm_abc));
    }
 
    // Function for binary search to find the
    // nth term divisible by a, b or c
    static long findNthTerm(int a, int b,
                            int c, long n)
    {
         
        // Set low to (gcd(a, b, c) * n) and high to (max(a, b, c) * n)
        // (gcd(a, b, c) * n) is lowest possible value till index 'n'
        // (max(a, b, c) * n) is highest possible value till index 'n'
        preCal(a, b, c);
        long low = 1, high, mid;
        high = a > b ? (a > c ? a : c) : (b > c ? b : c);
          high = high * n;
        low = gcd(a, gcd_bc) * n;
 
        while (low < high)
        {
            mid = low + (high - low) / 2;
 
            // If the current term is less than
            // n then we need to increase low
            // to mid + 1
            if (divTermCount(a, b, c, mid) < n)
            {
                low = mid + 1;
            }
             
            // If current term is greater than equal to
            // n then high = mid
            else
            {
                high = mid;
            }
        }
        return low;
    }
 
    // Driver code
    public static void Main(String []args)
    {
        int a = 2, b = 3, c = 5, n = 100;
 
        Console.WriteLine(findNthTerm(a, b, c, n));
    }
}
 
// This code is contributed by PrinciRaj1992
// This code was improved by sharad_jain

<script>
 
// Javascript program to find nth term
// divisible by a, b or c
 
// Function to return
// gcd of a and b
function gcd( a,  b)
{
    if (a == 0)
        return b;
 
    return gcd(b % a, a);
}
 
var gcd_ab, gcd_bc, gcd_ac, lcm_abc, lcm_ab, lcm_bc, lcm_ac;
 
function preCal(a, b, c) {
    gcd_ab = gcd(a, b); // GCD of a, b
    gcd_bc = gcd(c, b); // GCD of b, c
    gcd_ac = gcd(a, c); // GCD of a, c
    lcm_ab = ((a * b) / gcd_ab); // LCM of a, b
    lcm_bc = ((c * b) / gcd_bc); // LCM of b, c
    lcm_ac = ((a * c) / gcd_ac); // LCM of a, c
    lcm_abc = (lcm_ab * c) / gcd(lcm_ab, c); // LCM of a, b, c
}
 
// Function to return the count of integers
// from the range [1, num] which are
// divisible by either a, b or c
function divTermCount( a,  b,  c,  num)
{
    // Calculate the number of terms divisible by a, b
    // and c then remove the terms which are divisible
    // by both (a, b) or (b, c) or (c, a) and then
    // add the numbers which are divisible by a, b and c
    return parseInt((num / a) + (num / b) + (num / c)
            - (num / lcm_ab)
            - (num / lcm_bc)
            - (num / lcm_ac)
            + (num / lcm_abc));
}
 
// Function for binary search to find the
// nth term divisible by a, b or c
function findNthTerm( a,  b,  c,  n)
{
    // Set low to (gcd(a, b, c) * n) and high to (max(a, b, c) * n)
      // (gcd(a, b, c) * n) is lowest possible value till index 'n'
      // (max(a, b, c) * n) is highest possible value till index 'n'
    preCal(a, b, c);
    var low = 1, high, mid;
    high = a > b ? (a > c ? a : c) : (b > c ? b : c);
    high = high * n;
    low = gcd(a, gcd_bc) * n;
 
    while (low < high) {
        mid = low + (high - low) / 2;
 
        // If the current term is less than
        // n then we need to increase low
        // to mid + 1
        if (divTermCount(a, b, c, mid) < n)
            low = mid + 1;
 
        // If current term is greater than equal to
        // n then high = mid
        else
            high = mid;
    }
 
    return low;
}
 
var a = 2, b = 3, c = 5, n = 100;
document.write(parseInt(findNthTerm(a, b, c, n)));
 
 
// This code is contributed by SoumikMondal
// This code was improved by sharad_jain
 
</script>

136

Complejidad de tiempo: O(logn + log(min(a, b))

Espacio Auxiliar: O(1)