Autor Tema: Múltiplos

0 Usuarios y 1 Visitante están viendo este tema.

06 Mayo, 2010, 04:20 pm
Leído 1214 veces

plc

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 21
  • Karma: +0/-0
Dado un pequeño grupo de C números \( 1\le C\le 20 \) y un entero N, no necesariamente pequeño \( 1 \le N \le 2^{63-1} \), determine cuántos múltiplos de cualquiera de los C números hay desde 1 hasta N.

Esto es un problema para programarlo pero si hay alguna sugerencia matemática que me ayude a optimizar el tiempo? :-\


06 Mayo, 2010, 04:37 pm
Respuesta #1

administrador

  • Administrador
  • Mensajes: 1,595
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Hola plc

Como puedes ver te hemos puesto tus desigualdades utilizando el Latex.
Dedica 10 minutos a la lectura del instructivo, de manera que en lo siguiente puedas escribir tus fórmulas de la manera usual.
El instructivo:
http://rinconmatematico.com/foros/index.php/topic,870.0.html

06 Mayo, 2010, 10:30 pm
Respuesta #2

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 En realidad dado un número de \( C \) es fácil calcular de manera exacta cuantos múltiplos hay entre \( 1 \) y \( N \). Serían:

 \( f(C)=\left[\dfrac{N}{C}\right] \)

 siendo \( [x] \) la función parte entera.

 Supongamos ahora que queremos calcular los múltiplos a alguno dos números \( c_1,c_2 \) dados.

 No vale tomar \( f(c_1)+f(c_2) \) porque contaríamos dos veces los múltiplos comunes. Estos hay que descontararlos por lo que nos queda:

 \( f(c_1)+f(c_2)-f(m.c.m(c_1,c_2)) \)

 Siendo m.c.m el mínimo común múltiplo.

 Para tres números sería:

 \( f(c_1)+f(c_2)+f(c_3)-f(m.c.m(c_1,c_2))-f(m.c.m(c_1,c_3))-f(m.c.m(c_2,c_3))+ \)

\( +f(m.c.m(c_1,c_2,c_3)) \)

 (consecuencia del principio de inclusión-exclusión).

 En general para \( k \) números sería:

\( \displaystyle\sum_{i=1}^k{}f(c_i)-\displaystyle\sum_{1\leq i_1<i_2\leq k}f(m.c.m(c_{i_1},c_{i_2}))+ \)

\( -\displaystyle\sum_{1\leq i_1<i_2<i_3\leq k}f(m.c.m(c_{i_1},c_{i_2},c_{i_3}))+\ldots  \)

\( +\ldots-(-1)^kf(m.c.m(c_1,c_2,\ldots,c_k)) \)

Saludos.