Dados tres números enteros N, A, B, la tarea es encontrar el resto cuando la suma de los números enteros que son divisibles por A o B en el rango [1, N] se divide por el número de números enteros en este rango.
Nota: Los números A y B son coprimos.
Ejemplos:
Entrada: N = 88, A = 11, B = 8
Salida: 8
Explicación:
Hay un total de 18 números en el rango [1, 88] que son divisibles por 8 o por 11. Son:
{ 8, 11, 16, 22, 24, 32, 33, 40, 44, 48, 55, 56, 64, 66, 72, 77, 80, 88}. Por lo tanto, la suma de estos números es 836. Por lo tanto, 836 % 18 = 8.
Entrada: N = 100, A = 7, B = 19
Salida: 13
Explicación:
Hay un total de 19 números en el rango [1, 100 ] que son divisibles por 7 o por 19. Son:
{ 7, 14, 19, 21, 28, 35, 38, 42, 49, 56, 57, 63, 70, 76, 77, 84, 91, 95, 98}. Por lo tanto, la suma de estos números es 1020. Por lo tanto, 1020 % 19 = 13.
Enfoque ingenuo: el enfoque ingenuo consiste en ejecutar un bucle de 1 a N y contar todos los números que son divisibles por A o B mientras se suman simultáneamente esos números en una variable para encontrar su suma.
Complejidad de tiempo: O(N)
Enfoque eficiente: El enfoque eficiente es usar el método de división.
- Usando el método de división, la cuenta de los números que son divisibles por A o B se puede encontrar en el tiempo constante. La idea es:
- Divida N por A para obtener el número de números divisibles por A en el rango [1, N].
- Divida N por B para obtener el conteo de números divisibles por B en el rango [1, N].
- Divida N por A * B para obtener el número de números divisibles por A y B.
- Sume los valores obtenidos en el paso 1 y el paso 2 y reste el valor obtenido en el paso 3 para eliminar los números que se han contado dos veces.
- Como incluso estamos interesados en encontrar los números que son divisibles en este rango, la idea es reducir la cantidad de veces que se verifican las condiciones de la siguiente manera:
- En lugar de confiar completamente en un bucle, podemos usar dos bucles .
- Un bucle es encontrar los números divisibles por A. En lugar de incrementar los valores en 1, comenzamos el bucle desde A y lo incrementamos en A. Esto reduce drásticamente el número de comparaciones.
- De manera similar, se usa otro bucle para encontrar los números divisibles por B .
- Dado que nuevamente, puede haber repeticiones en los números, los números se almacenan en un conjunto para que no haya repeticiones.
- Una vez que se encuentran el conteo y la suma de los números, se puede aplicar directamente la operación de módulo para calcular la respuesta final.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the above approach
#include <algorithm>
#include <iostream>
#include <set>
#define ll long long
using namespace std;
// Function to return the count of numbers
// which are divisible by both A and B in
// the range [1, N] in constant time
ll int countOfNum(ll int n, ll int a, ll int b)
{
ll int cnt_of_a, cnt_of_b, cnt_of_ab, sum;
// Compute the count of numbers divisible by
// A in the range [1, N]
cnt_of_a = n / a;
// Compute the count of numbers divisible by
// B in the range [1, N]
cnt_of_b = n / b;
// Adding the counts which are
// divisible by A and B
sum = cnt_of_b + cnt_of_a;
// The above value might contain repeated
// values which are divisible by both
// A and B. Therefore, the count of numbers
// which are divisible by both A and B are found
cnt_of_ab = n / (a * b);
// The count computed above is subtracted to
// compute the final count
sum = sum - cnt_of_ab;
return sum;
}
// Function to return the sum of numbers
// which are divisible by both A and B
// in the range [1, N]
ll int sumOfNum(ll int n, ll int a, ll int b)
{
ll int i;
ll int sum = 0;
// Set to store the numbers so that the
// numbers are not repeated
set<ll int> ans;
// For loop to find the numbers
// which are divisible by A and insert
// them into the set
for (i = a; i <= n; i = i + a) {
ans.insert(i);
}
// For loop to find the numbers
// which are divisible by A and insert
// them into the set
for (i = b; i <= n; i = i + b) {
ans.insert(i);
}
// For loop to iterate through the set
// and find the sum
for (auto it = ans.begin();
it != ans.end(); it++) {
sum = sum + *it;
}
return sum;
}
// Driver code
int main()
{
ll int N = 88;
ll int A = 11;
ll int B = 8;
ll int count = countOfNum(N, A, B);
ll int sumofnum = sumOfNum(N, A, B);
cout << sumofnum % count << endl;
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
// Function to return the count of numbers
// which are divisible by both A and B in
// the range [1, N] in constant time
class GFG
{
static int countOfNum( int n, int a, int b)
{
int cnt_of_a, cnt_of_b, cnt_of_ab, sum;
// Compute the count of numbers divisible by
// A in the range [1, N]
cnt_of_a = n / a;
// Compute the count of numbers divisible by
// B in the range [1, N]
cnt_of_b = n / b;
// Adding the counts which are
// divisible by A and B
sum = cnt_of_b + cnt_of_a;
// The above value might contain repeated
// values which are divisible by both
// A and B. Therefore, the count of numbers
// which are divisible by both A and B are found
cnt_of_ab = n / (a * b);
// The count computed above is subtracted to
// compute the final count
sum = sum - cnt_of_ab;
return sum;
}
// Function to return the sum of numbers
// which are divisible by both A and B
// in the range [1, N]
static int sumOfNum( int n, int a, int b)
{
int i;
int sum = 0;
// Set to store the numbers so that the
// numbers are not repeated
Set< Integer> ans = new HashSet<Integer>();
// For loop to find the numbers
// which are divisible by A and insert
// them into the set
for (i = a; i <= n; i = i + a) {
ans.add(i);
}
// For loop to find the numbers
// which are divisible by A and insert
// them into the set
for (i = b; i <= n; i = i + b) {
ans.add(i);
}
// For loop to iterate through the set
// and find the sum
for (Integer it : ans) {
sum = sum + it;
}
return sum;
}
// Driver code
public static void main (String []args)
{
int N = 88;
int A = 11;
int B = 8;
int count = countOfNum(N, A, B);
int sumofnum = sumOfNum(N, A, B);
System.out.print(sumofnum % count);
}
}
// This code is contributed by chitranayal
Python3
# Python3 implementation of the above approach # Function to return the count of numbers # which are divisible by both A and B in # the range [1, N] in constant time def countOfNum(n, a, b): cnt_of_a, cnt_of_b, cnt_of_ab, sum = 0, 0, 0, 0 # Compute the count of numbers divisible by # A in the range [1, N] cnt_of_a = n // a # Compute the count of numbers divisible by # B in the range [1, N] cnt_of_b = n // b # Adding the counts which are # divisible by A and B sum = cnt_of_b + cnt_of_a # The above value might contain repeated # values which are divisible by both # A and B. Therefore, the count of numbers # which are divisible by both A and B are found cnt_of_ab = n // (a * b) # The count computed above is subtracted to # compute the final count sum = sum - cnt_of_ab return sum # Function to return the sum of numbers # which are divisible by both A and B # in the range [1, N] def sumOfNum(n, a, b): i = 0 sum = 0 # Set to store the numbers so that the # numbers are not repeated ans = dict() # For loop to find the numbers # which are divisible by A and insert # them into the set for i in range(a, n + 1, a): ans[i] = 1 # For loop to find the numbers # which are divisible by A and insert # them into the set for i in range(b, n + 1, b): ans[i] = 1 # For loop to iterate through the set # and find the sum for it in ans: sum = sum + it return sum # Driver code if __name__ == '__main__': N = 88 A = 11 B = 8 count = countOfNum(N, A, B) sumofnum = sumOfNum(N, A, B) print(sumofnum % count) # This code is contributed by mohit kumar 29
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the count of numbers
// which are divisible by both A and B in
// the range [1, N] in constant time
static int countOfNum( int n, int a, int b)
{
int cnt_of_a, cnt_of_b, cnt_of_ab, sum;
// Compute the count of numbers divisible by
// A in the range [1, N]
cnt_of_a = n / a;
// Compute the count of numbers divisible by
// B in the range [1, N]
cnt_of_b = n / b;
// Adding the counts which are
// divisible by A and B
sum = cnt_of_b + cnt_of_a;
// The above value might contain repeated
// values which are divisible by both
// A and B. Therefore, the count of numbers
// which are divisible by both A and B are found
cnt_of_ab = n / (a * b);
// The count computed above is subtracted to
// compute the readonly count
sum = sum - cnt_of_ab;
return sum;
}
// Function to return the sum of numbers
// which are divisible by both A and B
// in the range [1, N]
static int sumOfNum( int n, int a, int b)
{
int i;
int sum = 0;
// Set to store the numbers so that the
// numbers are not repeated
HashSet< int> ans = new HashSet<int>();
// For loop to find the numbers
// which are divisible by A and insert
// them into the set
for (i = a; i <= n; i = i + a) {
ans.Add(i);
}
// For loop to find the numbers
// which are divisible by A and insert
// them into the set
for (i = b; i <= n; i = i + b) {
ans.Add(i);
}
// For loop to iterate through the set
// and find the sum
foreach (int it in ans) {
sum = sum + it;
}
return sum;
}
// Driver code
public static void Main(String []args)
{
int N = 88;
int A = 11;
int B = 8;
int count = countOfNum(N, A, B);
int sumofnum = sumOfNum(N, A, B);
Console.Write(sumofnum % count);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the above approach
// Function to return the count of numbers
// which are divisible by both A and B in
// the range [1, N] in constant time
function countOfNum(n,a,b)
{
let cnt_of_a, cnt_of_b, cnt_of_ab, sum;
// Compute the count of numbers divisible by
// A in the range [1, N]
cnt_of_a = Math.floor(n / a);
// Compute the count of numbers divisible by
// B in the range [1, N]
cnt_of_b = Math.floor(n / b);
// Adding the counts which are
// divisible by A and B
sum = cnt_of_b + cnt_of_a;
// The above value might contain repeated
// values which are divisible by both
// A and B. Therefore, the count of numbers
// which are divisible by both A and B are found
cnt_of_ab = Math.floor(n / (a * b));
// The count computed above is subtracted to
// compute the final count
sum = sum - cnt_of_ab;
return sum;
}
// Function to return the sum of numbers
// which are divisible by both A and B
// in the range [1, N]
function sumOfNum(n,a,b)
{
let i;
let sum = 0;
// Set to store the numbers so that the
// numbers are not repeated
let ans = new Set();
// For loop to find the numbers
// which are divisible by A and insert
// them into the set
for (i = a; i <= n; i = i + a) {
ans.add(i);
}
// For loop to find the numbers
// which are divisible by A and insert
// them into the set
for (i = b; i <= n; i = i + b) {
ans.add(i);
}
// For loop to iterate through the set
// and find the sum
for (let it of ans.values()) {
sum = sum + it;
}
return sum;
}
// Driver code
let N = 88;
let A = 11;
let B = 8;
let count = countOfNum(N, A, B);
let sumofnum = sumOfNum(N, A, B);
document.write(sumofnum % count);
// This code is contributed by rag2127
</script>
Producción:
8
Análisis de la Complejidad del Tiempo:
- El tiempo necesario para ejecutar el ciclo for para encontrar los números que son divisibles por A es O(N / A) .
- El tiempo necesario para ejecutar el ciclo for para encontrar los números que son divisibles por B es O(N / B) .
- Por lo tanto, la complejidad temporal general es O(N / A) + O(N / B) .
Espacio Auxiliar: O(N/A + N/B)
Publicación traducida automáticamente
Artículo escrito por RishavSinghMehta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA