Problema

Calcular ~S_f(N)=\sum_{i=1}^Nf(i)~ donde ~f(i)~ es la cantidad de pares cuyo mínimo común múltiplo es ~i~.

Consideraciones iniciales.

• La función ~d(n)~ cuenta la cantidad de divisores de ~n~. Por ejemplo ~d(12)=6~, ~\{1,2,3,4,6,12\}~.
• La función ~\omega(n)~ cuenta la cantidad de factores primos de ~n~. Por ejemplo ~\omega(12)=2~, ~\{2,3\}~.
• La función ~\Omega(n)~ cuenta la cantidad de factores primos de ~n~ incluyendo sus multiplicidades. Por ejemplo ~\Omega(12)=3~, ~\{2_1,2_2,3_1\}~.
• La función de Möbius ~\mu(n)~ se define como: $$\displaystyle \mu(n)= \begin{cases} (-1)^{\omega(n)} & \text{si } \omega(n)=\Omega(n), \\ 0 & \text{si } \omega(n)<\Omega(n). \end{cases} $$

Soluciones

Subtarea 1: ~\sum N \leq 10^2~

La fórmula para calcular ~mcm(a,b)~ es ~\frac{a \cdot b}{mcd(a,b)}~, el ~mcd(a,b)~ lo podemos calcular usando el Algoritmo de Euclides o la función built-in ~\_\_gcd(a,b)~ en ~C++~, en cualquier caso el costo computacional de esto sería de orden logarítmico. Entonces, en cada uno de los ~T~ casos, para cada ~k~ entre ~1~ y ~N~ podemos calcular cuántos pares de números ~(a,b)~ con ~1 \leq a,b \leq k~ cumplen ~k=mcm(a,b)~ y luego sumar estas cantidades.

Complejidad: ~O(T+N^3 \cdot log(N))~.

Subtarea 2: ~\sum N \leq 10^3~

Sea ~F~ un arreglo donde inicialmente todas sus posiciones tienen el valor ~0~. Recorramos cada par ~(a,b)~ con ~1 \leq a,b \leq 10^3~ y aumentemos ~1~ en la posición ~mcm(a,b)~ del arreglo ~F~, este precómputo permite almacenar en la ~i~-ésima posición del arreglo ~F~ la cantidad de pares ~(a,b)~ tal que ~i=mcm(a,b)~, note que no nos interesa guardar valores en el arreglo después de la posición ~10^3~. El siguiente paso sería guardar la suma de cada prefijo de ~F~ en otro arreglo ~P~. Luego para ~N~ en cada uno de los ~T~ casos tenemos en la posición ~N~ de ~P~ la respuesta.

Complejidad: ~O(T+N^2 \cdot log(N))~.

Subtarea 3: ~\sum N \leq 10^4~

Considere precalcular el ~mcd~ de todos los pares ~(a,b)~ en una matriz ~M~ tal que ~M[a][b]=mcd(a,b)~, esto lo podemos hacer iterando por cada par ~(a,b)~, en el momento de calcular su ~mcd~ podemos usar el Algoritmo de Euclides, por la naturaleza recursiva del mismo podemos usar los valores ya guardados en ~M~, esto tiene complejidad ~O(N^2)~. Luego, considere la misma idea empleada en la Subtarea 2, pero ahora en vez de calcular ~mcd(a,b)~, tomamos el valor de ~M[a][b]~.

Complejidad: ~O(T+N^2)~.

Implementaciones eficientes de la idea comentada para resolver la Subtarea 2 son suficientes para obtener todos los puntos en la Subtarea 3.

Subtarea 4: ~\sum N \leq 10^6~

Considere la definición de ~mcm~ presentada en el planteamiento del problema, sea ~N=mcm(A,B)~, para un primo ~p_i~ de la factorización de ~N~ tenemos que su exponente ~e_i~ es ~max(a_i,b_i)~, donde ~a_i~ y ~b_i~ son los exponentes de ~p_i~ en la factorización de ~A~ y ~B~ respectivamente, calculemos de cuántas formas podemos elegir ~a_i~ y ~b_i~ de manera conveniente tal que ~e_i=max(a_i,b_i)~:

• ~e_i=a_i \Longrightarrow b_i~ puede tomar valores en el intervalo ~[0,e_i]~, estos son ~e_i+1~ valores diferentes
• ~e_i=b_i \Longrightarrow a_i~ puede tomar valores en el intervalo ~[0,e_i]~, estos son ~e_i+1~ valores diferentes

Note que el caso ~e_i=a_i=b_i~ se cuenta doble. Luego la cantidad de formas de fijar ~a_i~ y ~b_i~ tal que ~e_i=max(a_i,b_i)~ es ~(e_i+1)+(e_i+1)-1=2 \cdot e_i+1~. 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 ~A~ y ~B~ tal que ~mcm(A,B)=N~ es $$\displaystyle \prod (2 \cdot e_i + 1) $$ Sabemos que la cantidad de divisores de un número ~X=p_1^{z_1} \cdot p_2^{z_2} \cdot \ldots \cdot p_k^{z_k}~ es $$\displaystyle \prod_{i=1}^k (z_i + 1) $$ Con lo cual: $$\displaystyle n=p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_k^{e_k} \Longrightarrow \prod_{i=1}^k (2 \cdot e_i + 1) = d(n^2) \Longrightarrow S_f(n)=\sum_{i=1}^N d(i^2) $$ La función ~d(X^2)~ 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 ~i~ compuesto hasta ~10^6~ un valor ~r~ tal que ~1<r<i~, ~r\big|i~, ~s=\frac{i}{r}~ y ~mcd(r,s)=1~, luego ~d(i^2)=d(r^2) \cdot d(s^2)~; si ~i~ es primo, ~d(i^2)=3~. Guardemos esto en un arreglo ~D~ tal que ~D[i]=d(i^2)~. Luego podemos construir un arreglo ~P~ con la suma de los prefijos de ~D~. Para ~N~ en cada uno de los ~T~ casos la respuesta estaría en la ~N~-ésima posición de ~P~.

Complejidad: ~O(T + N \cdot log(N) \cdot log(log(N)))~.

Subtarea 5: ~\sum N \leq 10^7~

Con la misma idea de la subtarea anterior podemos emplear una criba lineal y computar ~r~ de manera eficiente.

Complejidad: ~O(N+T)~.

Subtarea 6: ~\sum N \leq 10^9~

Sabemos que: $$\displaystyle d(n^2) = \prod_{i=1}^k (2 \cdot e_i + 1) $$ Esta es una multiplicación de ~k~ binomios con lo cual podemos aplicar la propiedad distributiva respecto a la suma. Note que esta distribución es una suma de ~2^k~ multiplicaciones, donde cada una de estas multiplicaciones tiene entre sus factores exactamente uno de los términos de cada binomio (~2 \cdot e_i~ o ~1~), con lo cual cada multiplicación de estas puede ser representada como una máscara de bits, en la cual si el ~i~-ésimo bit está encendido significa que el ~i~-ésimo binomio aportó el factor ~2 \cdot e_i~ en caso contrario aportó el factor ~1~. De manera general, sea ~S~ el conjunto de las posiciones con bits encendidos en la máscara que le corresponde al ~i~-ésimo término después de aplicar la propiedad distributiva, este término es de la forma ~2^{|S|} \cdot e_{S_1} \cdot e_{S_2} \cdot \ldots \cdot e_{S_k}~, luego: $$\displaystyle \prod_{i=1}^k(2 \cdot e_i+1)=\sum_{S\subseteq\{1,2,\ldots,k \}}2^{|S|} \cdot \prod_{i \in S}e_i $$ De la fórmula anterior podemos deducir que ~\prod_{i \in S}e_i~ es la cantidad de divisores de ~n~ con exactamente ~|S|~ factores primos, luego: $$\displaystyle \sum_{S\subseteq\{1,2,\ldots,k \}}2^{|S|} \cdot \prod_{i \in S}e_i = \sum_{d|n} 2^{\omega(d)} $$ Observa que ~2^{\omega(d)}~ cuenta la cantidad de maneras en que se pueden formar subconjuntos a partir de los factores primos de ~d~. Además, cada uno de estos subconjuntos corresponde precisamente al conjunto de factores primos de algún divisor de ~d~. Sin embargo, debido a la posible multiplicidad de los factores primos, varios divisores de ~d~ pueden compartir el mismo subconjunto de factores primos. Entonces iterando sobre los divisores de ~d~ conseguimos recorrer cada posible subconjunto de factores primos que se cuenta con ~2^{\omega(d)}~, 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: $$\displaystyle 2^{\omega(d)}=\sum_{j|d} \mu^2(j) $$ Sintetizando: $$\displaystyle S_f(N)=\sum_{i=1}^Nd(i^2)=\sum_{i=1}^N\sum_{d|i} 2^{\omega(d)}=\sum_{i=1}^N\sum_{d|i} \sum_{j|d} \mu^2(j) $$ Reduciendo la expresión, podemos iterar sobre ~d~ teniendo en cuenta que es divisor de ~\lfloor \frac{N}{d} \rfloor~ enteros hasta ~N~: $$\displaystyle \sum_{i=1}^N\sum_{d|i} \sum_{j|d} \mu^2(j)=\sum_{d=1}^N \Bigl \lfloor \frac{N}{d} \Bigr \rfloor \sum_{j|d} \mu^2(j) $$ De manera análoga para ~j~: $$\displaystyle \sum_{d=1}^N \Bigl\lfloor\frac{N}{d} \Bigr \rfloor\sum_{j|d} \mu^2(j)=\sum_{j=1}^N \mu^2(j)\sum_{i=1}^{\lfloor \frac{N}{j} \rfloor} \Bigl \lfloor \frac{N}{ij} \Bigr \rfloor $$ Concluyendo: $$\displaystyle S_f(N)=\sum_{j=1}^N \mu^2(j) \sum_{i=1}^{\lfloor \frac{N}{j} \rfloor} \Bigl \lfloor \frac{N}{ij} \Bigr \rfloor $$ Para la simplicidad del cálculo dividamos la expresión en dos funciones: $$\displaystyle F(n)=\sum_{i=1}^n \mu^2(i) $$ $$\displaystyle G(n)=\sum_{i=1}^n \Bigl \lfloor \frac{n}{i} \Bigr \rfloor $$

Análisis para ~F(n)~.

La función de Möbius cumple: $$\displaystyle \sum_{d\mid n}\mu(d) = \begin{cases} 1 & \text{si } n = 1, \\ 0 & \text{si } n > 1. \end{cases} $$ Por tanto: $$\displaystyle \sum_{d^2\mid n}\mu(d) = \begin{cases} 1 & \text{si } n\text{ es libre de cuadrados}, \\ 0 & \text{si } n\text{ no es libre de cuadrados}. \end{cases} $$ Luego: $$\displaystyle \mu^2(n)=\sum_{d^2|n}\mu(d) \Longrightarrow \sum_{i=1}^n \mu^2(i) = \sum_{i=1}^n \sum_{d^2|i}\mu(d) $$ Reexpresando: $$\displaystyle \sum_{i=1}^n \sum_{d^2|i}\mu(d) = \sum_{d=1}^{\sqrt{n}} \mu(d) \Bigl \lfloor \frac{n}{d^2} \Bigr \rfloor $$ $$\displaystyle F(n)=\sum_{d=1}^{\sqrt{n}} \mu(d) \Bigl \lfloor \frac{n}{d^2} \Bigr \rfloor $$ Podemos computar ~F(n)~ con complejidad ~O(\sqrt{n})~.

Análisis para ~G(n)~.

Note que para todo ~i \leq \sqrt{n}~ la expresión ~\lfloor \frac{n}{i} \rfloor~ no toma más de ~\sqrt{n}~ valores distintos, además, para los ~i > \sqrt{n}~ se cumple ~\lfloor \frac{n}{i} \rfloor \leq \sqrt{n}~ por lo que no toma mas de ~\sqrt{n}~ valores distintos. Entonces para todo ~i~ (~1 \leq i \leq n~) se cumple que ~\lfloor \frac{n}{i} \rfloor~ no toma mas de ~2 \sqrt{n}~ valores distintos. Luego: $$\displaystyle G(n)=\sum_{i=1}^n \Bigl \lfloor \frac{n}{i} \Bigr \rfloor= \sum_{i=1}^{\sqrt{n}} \Bigl \lfloor \frac{n}{i} \Bigr \rfloor + \sum_{i=1}^{\Bigl \lfloor \frac{n}{\lfloor \sqrt{n} \rfloor+1} \Bigr \rfloor} i \Big( \Bigl \lfloor \frac{n}{i} \Bigr \rfloor - \Bigl \lfloor \frac{n}{i+1} \Bigr \rfloor \Big) $$ Podemos computar ~G(n)~ con complejidad ~O(\sqrt{n})~.

Análisis para ~S_f(n)~.

Recordemos que: $$\displaystyle S_f(N)=\sum_{j=1}^N \mu^2(j) \sum_{i=1}^{\lfloor \frac{N}{j} \rfloor} \Bigl \lfloor \frac{N}{ij} \Bigr \rfloor $$ De un análisis homólogo al que hicimos con la función ~G~ tenemos, para ~L=\sqrt{N}~: \[ \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 ~\mu~ hasta ~\sqrt{N}~ para la primera sumatoria.

Note que estas sumatorias iteran hasta ~\sqrt{N}~ pero dependen de funciones del mismo orden de complejidad.

Análisis de complejidad computacional.

Sea ~T(n)~ el costo total de nuestro algoritmo: $$\displaystyle T(n) \in O \Bigg( \sum_{i=1}^{\sqrt{N}}\sqrt{\frac{N}{i}}\Bigg) $$ Entonces: $$\displaystyle \sum_{i=1}^{\sqrt{N}}\sqrt{\frac{N}{i}} =\sqrt{N} \sum_{i=1}^{\sqrt{N}}\frac{1}{\sqrt{i}}< \sqrt{N} \sum_{i=1}^{\sqrt{N}} \frac{1}{\lfloor \sqrt{i} \rfloor} $$ Note que ~\lfloor \sqrt{i} \rfloor~ da el mismo resultado para los valores en el intervalo ~\big[ \lfloor\sqrt{i}\rfloor^2 ,(\lfloor\sqrt{i}\rfloor+1)^2-1 \big]~, estos son ~2\lfloor\sqrt{i}\rfloor+1~ valores, sea ~j=\lfloor\sqrt{i}\rfloor~: $$\displaystyle \sum_{i=1}^{\sqrt{N}}\sqrt{\frac{N}{i}} <\sqrt{N} \sum_{j=1}^{\sqrt[4]{N}}(2 \cdot j+1)\cdot \frac{1}{j} = \sqrt{N} \sum_{j=1}^{\sqrt[4]{N}}(2+\frac{1}{j}) < \sqrt{N} \sum_{j=1}^{\sqrt[4]{N}}3 = 3 \cdot \sqrt{N} \cdot \sqrt[4]{N} = 3 \cdot N^{\frac{3}{4}} $$ Finalmente: $$\displaystyle T(n) \in O\big(N^{\frac{3}{4}}\big) $$

Complejidad: ~O\big(T+N^{\frac{3}{4}}\big)~.

Subtarea 7: ~\sum N \leq 10^{11}~

Basándonos en la idea de la subtarea anterior.

Observe que la función ~G(n)~: $$\displaystyle G(n)=\sum_{i=1}^n \Bigl \lfloor \frac{n}{i} \Bigr \rfloor $$ Calcula en cada iteración la cantidad de divisores de ~i~ que son menores o iguales que ~n~, por tanto: $$\displaystyle G(n)=\sum_{i=1}^n d(i) $$ Sabemos que ~d(n)~ es una función multiplicativa.

Por tanto con una criba lineal podemos precalcular los valores de ~d~ y los valores de ~\mu~ hasta ~K~, entonces podemos resolver ~F(n)~ y ~G(n)~ en ~O(1)~ para cada ~n \leq K~. Tomemos ~K=N^{\frac{2}{3}}~, para ~n \leq K~ el algoritmo tiene complejidad ~O\big(N^{\frac{2}{3}}\big)~, para ~n>K~ tenemos: $$\displaystyle O\Bigg( \sum_{i=1}^{\sqrt[3]{N}}\sqrt{\frac{N}{i}}\Bigg) $$ De manera análoga a la demostración de complejidad en la subtarea anterior: $$\displaystyle \sum_{i=1}^{\sqrt[3]{N}}\sqrt{\frac{N}{i}}=\ldots=3 \cdot \sqrt{N} \cdot \sqrt[6]{N} = 3 \cdot N^{\frac{2}{3}} $$ Esto también es ~O\big(N^{\frac{2}{3}}\big)~.

Complejidad: ~O\big(T+N^{\frac{2}{3}}\big)~.