Editorial for MCM-SUM
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Problema
Calcular donde
es la cantidad de pares cuyo mínimo común múltiplo es
.
Consideraciones iniciales.
- La función
cuenta la cantidad de divisores de
. Por ejemplo
,
.
- La función
cuenta la cantidad de factores primos de
. Por ejemplo
,
.
- La función
cuenta la cantidad de factores primos de
incluyendo sus multiplicidades. Por ejemplo
,
.
- La función de Möbius
se define como:
Soluciones
Subtarea 1: 
La fórmula para calcular es
, el
lo podemos calcular usando el Algoritmo de Euclides o la función built-in
en
, en cualquier caso el costo computacional de esto sería de orden logarítmico. Entonces, en cada uno de los
casos, para cada
entre
y
podemos calcular cuántos pares de números
con
cumplen
y luego sumar estas cantidades.
Complejidad: .
Subtarea 2: 
Sea un arreglo donde inicialmente todas sus posiciones tienen el valor
. Recorramos cada par
con
y aumentemos
en la posición
del arreglo
, este precómputo permite almacenar en la
-ésima posición del arreglo
la cantidad de pares
tal que
, note que no nos interesa guardar valores en el arreglo después de la posición
. El siguiente paso sería guardar la suma de cada prefijo de
en otro arreglo
. Luego para
en cada uno de los
casos tenemos en la posición
de
la respuesta.
Complejidad: .
Subtarea 3: 
Considere precalcular el de todos los pares
en una matriz
tal que
, esto lo podemos hacer iterando por cada par
, en el momento de calcular su
podemos usar el Algoritmo de Euclides, por la naturaleza recursiva del mismo podemos usar los valores ya guardados en
, esto tiene complejidad
. Luego, considere la misma idea empleada en la Subtarea 2, pero ahora en vez de calcular
, tomamos el valor de
.
Complejidad: .
Implementaciones eficientes de la idea comentada para resolver la Subtarea 2 son suficientes para obtener todos los puntos en la Subtarea 3.
Subtarea 4: 
Considere la definición de presentada en el planteamiento del problema, sea
, para un primo
de la factorización de
tenemos que su exponente
es
, donde
y
son los exponentes de
en la factorización de
y
respectivamente, calculemos de cuántas formas podemos elegir
y
de manera conveniente tal que
:
puede tomar valores en el intervalo
, estos son
valores diferentes
puede tomar valores en el intervalo
, estos son
valores diferentes
Note que el caso se cuenta doble. Luego la cantidad de formas de fijar
y
tal que
es
.
Además los exponentes de los primos se fijan de manera independiente, por tanto por principio de multiplicación la cantidad de formas de tomar
y
tal que
es
Sabemos que la cantidad de divisores de un número
es
Con lo cual:
La función
es una función multiplicativa (la demostración queda propuesta al lector, esta sale trivialmente de la definición), podemos aprovecharnos de este hecho. Auxiliándonos de una criba podemos hallar para cada número
compuesto hasta
un valor
tal que
,
,
y
, luego
; si
es primo,
. Guardemos esto en un arreglo
tal que
. Luego podemos construir un arreglo
con la suma de los prefijos de
. Para
en cada uno de los
casos la respuesta estaría en la
-ésima posición de
.
Complejidad: .
Subtarea 5: 
Con la misma idea de la subtarea anterior podemos emplear una criba lineal y computar de manera eficiente.
Complejidad: .
Subtarea 6: 
Sabemos que:
Esta es una multiplicación de
binomios con lo cual podemos aplicar la propiedad distributiva respecto a la suma. Note que esta distribución es una suma de
multiplicaciones, donde cada una de estas multiplicaciones tiene entre sus factores exactamente uno de los términos de cada binomio (
o
), con lo cual cada multiplicación de estas puede ser representada como una máscara de bits, en la cual si el
-ésimo bit está encendido significa que el
-ésimo binomio aportó el factor
en caso contrario aportó el factor
. De manera general, sea
el conjunto de las posiciones con bits encendidos en la máscara que le corresponde al
-ésimo término después de aplicar la propiedad distributiva, este término es de la forma
, luego:
De la fórmula anterior podemos deducir que
es la cantidad de divisores de
con exactamente
factores primos, luego:
Observa que
cuenta la cantidad de maneras en que se pueden formar subconjuntos a partir de los factores primos de
. Además, cada uno de estos subconjuntos corresponde precisamente al conjunto de factores primos de algún divisor de
. Sin embargo, debido a la posible multiplicidad de los factores primos, varios divisores de
pueden compartir el mismo subconjunto de factores primos. Entonces iterando sobre los divisores de
conseguimos recorrer cada posible subconjunto de factores primos que se cuenta con
, pero por la posible multiplicidad de estos factores estaríamos contando varias veces el mismo subconjunto, para evitar esto usemos la función de Möbius:
Sintetizando:
Reduciendo la expresión, podemos iterar sobre
teniendo en cuenta que es divisor de
enteros hasta
:
De manera análoga para
:
Concluyendo:
Para la simplicidad del cálculo dividamos la expresión en dos funciones:
Análisis para
.
La función de Möbius cumple:
Por tanto:
Luego:
Reexpresando:
Podemos computar
con complejidad
.
Análisis para
.
Note que para todo la expresión
no toma más de
valores distintos, además, para los
se cumple
por lo que no toma mas de
valores distintos. Entonces para todo
(
) se cumple que
no toma mas de
valores distintos. Luego:
Podemos computar
con complejidad
.
Análisis para
.
Recordemos que:
De un análisis homólogo al que hicimos con la función
tenemos, para
:
\[
\boxed{
S_f(n)=\sum_{j=1}^L \mu^2(j) \cdot G\Big(\frac{L}{j}\Big)+\sum_{j=1}^{\lfloor \frac{N}{L+1} \rfloor} \Big(F\Big(\frac{N}{j}\Big)-F\Big(\frac{N}{j+1}\Big)\Big) \cdot G(j)
}
\]
Precomputemos hasta
para la primera sumatoria.
Note que estas sumatorias iteran hasta pero dependen de funciones del mismo orden de complejidad.
Análisis de complejidad computacional.
Sea el costo total de nuestro algoritmo:
Entonces:
Note que
da el mismo resultado para los valores en el intervalo
, estos son
valores, sea
:
Finalmente:
Complejidad: .
Subtarea 7: 
Basándonos en la idea de la subtarea anterior.
Observe que la función :
Calcula en cada iteración la cantidad de divisores de
que son menores o iguales que
, por tanto:
Sabemos que
es una función multiplicativa.
Por tanto con una criba lineal podemos precalcular los valores de y los valores de
hasta
, entonces podemos resolver
y
en
para cada
. Tomemos
, para
el algoritmo tiene complejidad
, para
tenemos:
De manera análoga a la demostración de complejidad en la subtarea anterior:
Esto también es
.
Complejidad: .
Comments