Recuento de múltiplos de A, B o C menores o iguales a N

Dados cuatro números enteros N , A , B y C . La tarea es encontrar el número de enteros del rango [1, N] que son divisibles por A , B o C . 

Ejemplos: 

Entrada: A = 2, B = 3, C = 5, N = 10 
Salida: 8 
2, 3, 4, 5, 6, 8, 9 y 10 son los únicos números del 
rango [1, 10] que son divisibles por la cruz 2, 3 o 5.

Entrada: A = 7, B = 3, C = 5, N = 100 
Salida: 55 
 

Enfoque: Un enfoque eficiente es utilizar el concepto de teoría de conjuntos. Como tenemos que encontrar números que sean divisibles por a o b o c. 

• Sea n(a): cuenta de números divisibles por a.
• Sea n(b): cuenta de números divisibles por b.
• Sea n(c): cuenta de números divisibles por c.
• n(a ∩ b): cuenta de números divisibles por a y b.
• n(a ∩ c): cuenta de números divisibles por a y c.
• n(b ∩ c): cuenta de números divisibles por b y c.
• n(a ∩ b ∩ c): cuenta de números divisibles por a y b y c.

Según la teoría de conjuntos,

n(a ∪ segundo ∪ c) = n(a) + n(b) + n(c) – n(a ∩ b) – n(b ∩ c) – n(a ∩ c) + n(a ∩ segundo ∩c)

Asi que. la cuenta de números divisibles por A, B o C es (num/A) + (num/B) + (num/C) – (num/mcm(A, B)) – (num/mcm(A, B) )) – (núm/mcm(A, C)) + – (núm/mcm(A, B, C))

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// gcd of a and b
long gcd(long a, long b)
{
    if (a == 0)
        return b;
 
    return gcd(b % a, a);
}
 
// 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 / ((a * b) / gcd(a, b)))
            - (num / ((c * b) / gcd(c, b)))
            - (num / ((a * c) / gcd(a, c)))
            + (num / ((a * b * c) / gcd(gcd(a, b), c))));
}
 
// Driver code
int main()
{
    long a = 7, b = 3, c = 5, n = 100;
 
    cout << divTermCount(a, b, c, n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
     
class GFG
{
     
// Function to return the
// gcd of a and b
static long gcd(long a, long b)
{
    if (a == 0)
        return b;
 
    return gcd(b % a, a);
}
 
// 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 / ((a * b) / gcd(a, b))) -
                (num / ((c * b) / gcd(c, b))) -
                (num / ((a * c) / gcd(a, c))) +
                (num / ((a * b * c) / gcd(gcd(a, b), c))));
}
 
// Driver code
static public void main (String []arr)
{
    long a = 7, b = 3, c = 5, n = 100;
 
    System.out.println(divTermCount(a, b, c, n));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
 
# Function to return the
# gcd of a and b
def gcd(a, b) :
 
    if (a == 0) :
        return b;
 
    return gcd(b % a, a);
 
def lcm (x, y):
    return (x * y) // gcd (x, y)
 
# 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 // lcm(a, b) -
                 num // lcm(c, b) -
                 num // lcm(a, c) +
                 num // (lcm(lcm(a, b), c)))
 
# Driver code
if __name__ == "__main__" :
 
    a = 7; b = 3; c = 5; n = 100;
 
    print(divTermCount(a, b, c, n));
 
# This code is contributed by AnkitRai01

// C# implementation for above approach
using System;
     
class GFG
{
     
// Function to return the
// gcd of a and b
static long gcd(long a, long b)
{
    if (a == 0)
        return b;
 
    return gcd(b % a, a);
}
 
// 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 / ((a * b) / gcd(a, b))) -
            (num / ((c * b) / gcd(c, b))) -
            (num / ((a * c) / gcd(a, c))) +
            (num / ((a * b * c) / gcd(gcd(a, b), c))));
}
 
// Driver code
static public void Main (String []arr)
{
    long a = 7, b = 3, c = 5, n = 100;
 
    Console.WriteLine(divTermCount(a, b, c, n));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
// Function to return the
// gcd of a and b
function gcd(a, b)
{
    if (a == 0)
        return b;
 
    return gcd(b % a, a);
}
 
// 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 Math.ceil(((num / a) + (num / b) + (num / c) -
                      (num / ((a * b) / gcd(a, b))) -
                      (num / ((c * b) / gcd(c, b))) -
                      (num / ((a * c) / gcd(a, c))) +
                      (num / ((a * b * c) / gcd(gcd(a, b), c)))));
}
 
// Driver code
n = 13;
var a = 7, b = 3, c = 5, n = 100;
 
document.write(divTermCount(a, b, c, n));
 
// This code is contributed by SoumikMondal
 
</script>

55

Complejidad de tiempo: O(log(min(a, b))), donde a y b son los parámetros de gcd

Espacio Auxiliar: O(1)