# Popcount Sum - Solución
Hallar e imprimir el valor de la siguiente suma:

$$
\sum_{
1 \leq i \leq N \\
i \% M = R
}popcount(i)
$$

donde $popcount(x)$ es igual a la cantidad de bits en $x$ con valor $1$.

## Solución
Primero notemos que si $i$ cumple que $i \% M = R$ se puede expresar como $i=k \cdot M+R$, para un entero $k$, por el algoritmo de la división. Modifiquemos la expresión de la suma para iterar sobre $k$:

$$
\sum_{k=0}^{\lfloor \frac{N-R}{M} \rfloor}popcount(k \cdot M + R)
$$

El límite superior de la suma es $\lfloor \frac{N-R}{M} \rfloor$, ya que se debe cumplir que $k \cdot M + R \leq N$. Al despejar $k$ obtenemos $k \leq \lfloor \frac{N-R}{M} \rfloor$.

Ahora, expresemos $popcount(x)$ mediante una expresión matemática para una $x$ de tipo `int`:

$$
popcount(x)=\sum_{b=0}^{31}isSet(x,b)
$$

donde:

$$
\begin{equation}
isSet(x,b)=
\begin{cases}
1 & \text{si el b-ésimo bit está prendido en x}\\
0 & \text{en caso contrario}
\end{cases}
\end{equation}
$$

Existen varias formas de expresar $isSet(x,b)$ mediante una expresión, aquí hay tres ejemplos:

$isSet(x,b)=(x >> b) \& 1$

$isSet(x,b)=\lfloor \frac{x}{2^b} \rfloor \% 2$

$isSet(x,b)=\lfloor \frac{x}{2^b} \rfloor -2 \cdot \lfloor \frac{x}{2^{b+1}} \rfloor$

Utilicemos la última y sustituyamosla en nuestro problema original:

$$
\sum_{k=0}^{\lfloor \frac{N-R}{M} \rfloor}popcount(k \cdot M + R) = \sum_{k=0}^{\lfloor \frac{N-R}{M} \rfloor} \sum_{b=0}^{31}isSet(k \cdot M + R,b)
$$
$$
=\sum_{k=0}^{\lfloor \frac{N-R}{M} \rfloor} \sum_{b=0}^{31}(\lfloor \frac{k \cdot M + R}{2^b} \rfloor -2 \cdot \lfloor \frac{k \cdot M + R}{2^{b+1}} \rfloor)
$$
$$
=\sum_{b=0}^{31} \sum_{k=0}^{\lfloor \frac{N-R}{M} \rfloor} (\lfloor \frac{k \cdot M + R}{2^b} \rfloor -2 \cdot \lfloor \frac{k \cdot M + R}{2^{b+1}} \rfloor)
$$
$$
=\sum_{b=0}^{31}( \sum_{k=0}^{\lfloor \frac{N-R}{M} \rfloor} \lfloor \frac{k \cdot M + R}{2^b} \rfloor - \sum_{k=0}^{\lfloor \frac{N-R}{M} \rfloor} 2 \cdot \lfloor \frac{k \cdot M + R}{2^{b+1}} \rfloor)
$$

Una suma de la forma $\sum_{i=0}^n \lfloor \frac{a \cdot i+b}{m} \rfloor$ es conocida como **Floor Sum** o Suma de Pisos y ya existe un método para hallar esta suma en $O(logn)$, por ejemplo, en el [reference de Alan](https://github.com/alaneos777/reference/blob/master/numberTheory.cpp#L1003).

Finalmente, la respuesta es la siguiente:

$$
\sum_{b=0}^{31}( f(M,R,2^b,\lfloor \frac{N-R}{M} \rfloor) - 2 \cdot f(M,R,2^{b+1},\lfloor \frac{N-R}{M} \rfloor) )
$$

donde $f(a,b,m,n)$ es la función de Floor Sum.

Complejidad: $O(log^2n)$