Encuentra la suma de todos los números entre 1 y N divisible por X o Y

Question

decir que tenemos 3 números N, x y y que son siempre >=1.

N será mayor que x y y y x será mayor que y.

Ahora necesitamos para encontrar la suma de todos los números entre 1 y N que son divisibles por x o y.

me ocurrió esto:

sum = 0; 
for(i=1;i<=N;i++) 
{ 
    if(i%x || i%y) 
    sum += i; 
} 

¿Hay una manera mejor manera de encontrar la suma evitando el bucle?

He estado golpeando mi cabeza por muchos días pero no he encontrado nada mejor.

Si el valor de N tiene un límite superior, podemos usar un método de búsqueda para acelerar el proceso.

Gracias a todos.

Quería una solución basada en C/C++. ¿Hay una función incorporada para hacer esto? ¿O tengo que codificar el algoritmo?

Answer 1

Sí. Puede anular el ciclo for por completo y encontrar la suma en tiempo constante.

De acuerdo con la Inclusion–exclusion principle sumando los múltiplos de x y múltiplos de y y restando el múltiple (s) común que consiguió dos veces añadido debe darnos la suma requerida.

Required Sum = sum of (multiples of x that are <= N) +  
       sum of (multiples of y that are <= N) - 
       sum of (multiples of (x*y) that are <= N) 

Ejemplo:

N = 15 
x = 3 
y = 4 

Required sum = (3 + 6 + 9 + 12 + 15) + // multiples of 3 
       (4 + 8 + 12) -   // multiples of 4 
       (12)     // multiples of 12 

Como se ha visto anteriormente tuvimos que restar 12 A medida que se añade dos veces porque es un múltiplo común.

¿Cómo es todo el algoritmo O (1)?

Let sum(x, N) sea suma de múltiplos de x que son menores o iguales a N.

sum(x,N) = x + 2x + ... + floor(N/x) * x 
     = x * (1 + 2 + ... + floor(N/x)) 
     = x * (1 + 2 + ... + k) // Where k = floor(N/x) 
     = x * k * (k+1)/2   // Sum of first k natural num = k*(k+1)/2 

Ahora k = floor(N/x) se pueden calcular en tiempo constante.

Una vez k se sabe sum(x,N) se puede calcular en tiempo constante.

Por lo tanto, la suma requerida también se puede calcular en tiempo constante.

EDIT:

La discusión anterior es válido sólo cuando x y y son co-primes.Si no, necesitamos usar LCM(x,y) en lugar de x*y. Hay muchas formas de encontrar LCM, una de las cuales es dividir el producto por GCD. Ahora GCD no se puede calcular en tiempo constante, pero su time complexity se puede hacer significativamente menor que el tiempo lineal.

Answer 2

Si un número es divisible por X, tiene que ser un múltiplo de x. Si un número es divisible por Y, tiene que ser un múltiplo de y.

Creo que si haces un bucle for para todos los múltiplos de xey, y evitas duplicados, deberías obtener la misma respuesta.

Fuera de mi cabeza, algo del tipo:

sum = 0 
for(i=x; i<=n; i+=x) 
    sum += i; 

for(i=y; i<=n; i+=y) 
    if(y % x != 0) 
     sum += i;