Cuente los divisores totales de A o B en un rango dado

Posted on by Rudeus Greyrat

Dados cuatro enteros m, n, a, b. Encuentra cuántos números enteros del rango m a n son divisibles por a o b. 
Ejemplos: 
 

Input: 3 11 2 3
Output: 6
Explanation:
m = 3, n = 11, a = 2, b = 3
There are total 6 numbers from 3 to 
11 which are divisible by 2 or 3 i.e, 
3, 4, 6, 8, 9, 10 

Input: arr[] = {11, 1000000, 6, 35}
Output: 190475

Un enfoque ingenuo es ejecutar un ciclo de m an y contar todos los números que son divisibles por a o b. La complejidad de tiempo de este enfoque será O(m – n) que definitivamente expirará para valores grandes de m.
Un enfoque eficiente es usar MCM simple y método de división. 
 

  1. Divida n por a para obtener el recuento total de todos los números (1 a n) divisibles por ‘a’. 
     
  2. Divida m-1 por a para obtener el recuento total de todos los números (1 a m-1) divisibles por ‘a’. 
     
  3. Reste la cuenta de los pasos 1 y 2 para obtener divisores totales en el rango de m a n. 
     

Ahora tenemos un número total de divisores de ‘a’ en el rango dado. Repita lo anterior para contar los divisores totales de ‘b’. 
Súmelos para obtener el recuento total de divisores ‘a’ y ‘b’. 
Pero el número divisible por a y b contó dos veces. Por lo tanto, para eliminar esta ambigüedad, podemos usar MCM de a y b para contar el número total divisible por ‘a’ y ‘b’. 
 

  1. Halla el MCM de ‘a’ y ‘b’. 
     
  2. Divida n por MCM para obtener el conteo de números (1 a n) divisibles por ‘a’ y ‘b’. 
     
  3. Divida m-1 por LCM para obtener el conteo de números (1 a m-1) divisibles por ‘a’ y ‘b’. 
     
  4. Reste la cuenta de los pasos 2 y 3 para obtener divisores totales de ‘a’ y ‘b’. 
     

Ahora reste este resultado del resultado calculado anterior para encontrar el recuento total de todos los divisores únicos de ‘a’ o ‘b’.
 

C++

// C++ program to count total divisors of 'a'
// or 'b' in a given range
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to find LCM of two numbers
int FindLCM(int a, int b)
{
    return (a * b) / __gcd(a, b);
}
 
// Function to calculate all divisors in given range
int rangeDivisor(int m, int n, int a, int b)
{
    // Find LCM of a and b
    int lcm = FindLCM(a, b);
 
    int a_divisor = n / a - (m - 1) / a;
    int b_divisor = n / b - (m - 1) / b;
 
    // Find common divisor by using LCM
    int common_divisor = n / lcm - (m - 1) / lcm;
 
    int ans = a_divisor + b_divisor - common_divisor;
    return ans;
}
 
// Driver code
int main()
{
    int m = 3, n = 11, a = 2, b = 3;
    cout << rangeDivisor(m, n, a, b) << endl;
 
    m = 11, n = 1000000, a = 6, b = 35;
    cout << rangeDivisor(m, n, a, b);
    return 0;
}

Java

// Java program to count total divisors of 'a'
// or 'b' in a given range
 
import java.math.BigInteger;
 
class Test
{
    // Utility method to find LCM of two numbers
    static int FindLCM(int a, int b)
    {
        return (a * b) / new BigInteger(a+"").gcd(new BigInteger(b+"")).intValue();
    }
     
    // method to calculate all divisors in given range
    static int rangeDivisor(int m, int n, int a, int b)
    {
        // Find LCM of a and b
        int lcm = FindLCM(a, b);
      
        int a_divisor = n / a - (m - 1) / a;
        int b_divisor = n / b - (m - 1) / b;
      
        // Find common divisor by using LCM
        int common_divisor = n / lcm - (m - 1) / lcm;
      
        int ans = a_divisor + b_divisor - common_divisor;
        return ans;
    }
     
    // Driver method
    public static void main(String args[])
    {
        int m = 3, n = 11, a = 2, b = 3;
        System.out.println(rangeDivisor(m, n, a, b));
      
        m = 11; n = 1000000 ; a = 6; b = 35;
        System.out.println(rangeDivisor(m, n, a, b));
    }
}

Python3

# python program to count total divisors
# of 'a' or 'b' in a given range
 
def __gcd(x, y):
 
    if x > y:
        small = y
    else:
        small = x
    for i in range(1, small+1):
        if((x % i == 0) and (y % i == 0)):
            gcd = i
             
    return gcd
     
# Utility function to find LCM of two
# numbers
def FindLCM(a, b):
    return (a * b) / __gcd(a, b);
 
 
# Function to calculate all divisors in
# given range
def rangeDivisor(m, n, a, b):
     
    # Find LCM of a and b
    lcm = FindLCM(a, b)
 
    a_divisor = int( n / a - (m - 1) / a)
    b_divisor = int(n / b - (m - 1) / b)
     
    # Find common divisor by using LCM
    common_divisor =int( n / lcm - (m - 1) / lcm)
 
    ans = a_divisor + b_divisor - common_divisor
    return ans
 
# Driver code
m = 3
n = 11
a = 2
b = 3;
print(rangeDivisor(m, n, a, b))
m = 11
n = 1000000
a = 6
b = 35
print(rangeDivisor(m, n, a, b))
 
# This code is contributed by Sam007

C#

// C# program to count total divisors
// of 'a' or 'b' in a given range
using System;
 
class GFG {
 
    static int GCD(int num1, int num2)
    {
        int Remainder;
 
        while (num2 != 0)
        {
            Remainder = num1 % num2;
            num1 = num2;
            num2 = Remainder;
        }
 
        return num1;
    }
     
    // Utility function to find LCM of
    // two numbers
    static int FindLCM(int a, int b)
    {
        return (a * b) / GCD(a, b);
    }
     
    // Function to calculate all divisors in given range
    static int rangeDivisor(int m, int n, int a, int b)
    {
        // Find LCM of a and b
        int lcm = FindLCM(a, b);
     
        int a_divisor = n / a - (m - 1) / a;
        int b_divisor = n / b - (m - 1) / b;
     
        // Find common divisor by using LCM
        int common_divisor = n / lcm - (m - 1) / lcm;
     
        int ans = a_divisor + b_divisor - common_divisor;
        return ans;
    }
         
    public static void Main ()
    {
        int m = 3, n = 11, a = 2, b = 3;
        Console.WriteLine(rangeDivisor(m, n, a, b));
 
        m = 11;    n = 1000000;
        a = 6; b = 35;
        Console.WriteLine(rangeDivisor(m, n, a, b));
    }
}
 
// This code is contributed by Sam007.

PHP

<?php
// PHP program to count total
// divisors of 'a' or 'b' in
// a given range
 
function gcd($a, $b)
{
    return ($a % $b) ?
    gcd($b, $a % $b) :
                   $b;
}
 
 
// Utility function to
// find LCM of two numbers
function FindLCM($a, $b)
{
    return ($a * $b) / gcd($a, $b);
}
 
// Function to calculate
// all divisors in given range
function rangeDivisor($m, $n, $a, $b)
{
    // Find LCM of a and b
    $lcm = FindLCM($a, $b);
 
    $a_divisor = $n / $a - ($m - 1) / $a;
    $b_divisor = $n / $b - ($m - 1) / $b;
 
    // Find common divisor by using LCM
    $common_divisor = $n / $lcm -
                          ($m - 1) / $lcm;
 
    $ans = $a_divisor + $b_divisor -
                        $common_divisor;
    return $ans;
}
 
// Driver Code
$m = 3;
$n = 11;
$a = 2;
$b = 3;
print(ceil(rangeDivisor($m, $n, $a, $b)));
echo "\n";
 
$m = 11;
$n = 1000000;
$a = 6;
$b = 35;
print(ceil(rangeDivisor($m, $n,$a,$b)));
 
// This code is contributed by Sam007
?>

Javascript

<script>
 
    // JavaScript program to count total divisors
    // of 'a' or 'b' in a given range
     
    function GCD(num1, num2)
    {
        let Remainder;
   
        while (num2 != 0)
        {
            Remainder = num1 % num2;
            num1 = num2;
            num2 = Remainder;
        }
   
        return num1;
    }
       
    // Utility function to find LCM of
    // two numbers
    function FindLCM(a, b)
    {
        return parseInt((a * b) / GCD(a, b), 10);
    }
       
    // Function to calculate all divisors in given range
    function rangeDivisor(m, n, a, b)
    {
        // Find LCM of a and b
        let lcm = FindLCM(a, b);
       
        let a_divisor = parseInt(n / a, 10) -
                        parseInt((m - 1) / a, 10);
                         
        let b_divisor = parseInt(n / b, 10) -
                        parseInt((m - 1) / b, 10);
       
        // Find common divisor by using LCM
        let common_divisor = parseInt(n / lcm, 10) -
                             parseInt((m - 1) / lcm, 10);
       
        let ans = a_divisor + b_divisor - common_divisor;
        return ans;
    }
     
    let m = 3, n = 11, a = 2, b = 3;
    document.write(rangeDivisor(m, n, a, b) + "</br>");
 
    m = 11;    n = 1000000;
    a = 6; b = 35;
    document.write(rangeDivisor(m, n, a, b));
     
</script>

Producción:  

6
190475

Complejidad temporal: O(log(MAX(a, b)) 
Espacio auxiliar: O(1) Shubham Bansal
contribuye con este artículo . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks. org o envíe su artículo por correo a review-team@geeksforgeeks.org Vea su artículo en la página principal de GeeksforGeeks y ayude a otros Geeks.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *