PKU 2800 - Joseph's Problem

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2800

Resumo

Dados inteiros $n$ e $k$, onde $1 \leq n, k \leq 10^9$, determinar o valor de $\sum_{1\leq i \leq n}{(k \mod i)}$.

Solução

Temos o seguinte:

$$ \begin{array}{rcl} \displaystyle\sum_{1\leq i \leq n}{(k \mod\ i)} & = & \displaystyle\sum_{1\leq i \leq n}{\left(k - \left\lfloor{\frac{k}{i}}\right\rfloor\ i \right)} \\ & = & nk - \displaystyle\sum_{1\leq i \leq n}{\left\lfloor{\frac{k}{i}}\right\rfloor\ i} \\ \end{array} $$

Agora reduzimos o problema a encontrar o valor de $\sum_{1\leq i \leq n}{(\lfloor{\frac{k}{i}}\rfloor\ i)}$.

Vamos analisar a seguinte instância: $n=11$, $k=11$.

$i$ 1 2 3 4 5 6 7 8 9 10 11
$\lfloor{\frac{k}{i}}\rfloor$ 11 5 3 2 2 1 1 1 1 1 1

Para essa instância o resultado é:

$$ \begin{array}{rcl} result & = & 11 \cdot 11 - (1 \cdot 11 + 2 \cdot 5 + 3 \cdot 3 + 4 \cdot 2 + 5 \cdot 2 + 6 \cdot 1 + 7 \cdot 1 + 8 \cdot 1 + 9 \cdot1 + 10 \cdot 1 + 11 \cdot 1) \\ & = & 11 \cdot 11 - [1 \cdot 11 + 5 \cdot 2 + 3 \cdot 3 + (4 + 5) \cdot 2 + (6 + 7 + 8 + 9 + 10 + 11) \cdot 1] \\ & = & 22 \end{array} $$

Você percebeu que alguns multiplicadores podem ser colocados em evidência, e que ao colocá-lo em evidência você pode calcular um grande número de parcelas em $O(1)$?

Isso nos sugere um algoritmo. Se $n > k$, as parcelas onde $i>k$ somam $0$, logo considere $n = k$. Dado que na computação do somatório estamos no termo $i$, podemos calcular de forma eficiente o menor $j$, tal que $\lfloor{\frac{k}{i}}\rfloor > \lfloor{\frac{k}{j}}\rfloor$ (se $j > n$, considere $j=n$). De posse de $i$ e $j$, podemos calcular a soma das parcelas $i, i+1, i+2, ..., j - 1$ em $O(1)$ e passar para próxima iteração com $i$ assumindo o valor de $j$.

Para calcular $j$ de forma eficiente podemos usar uma busca binária, pois a função $\lfloor{\frac{k}{i}}\rfloor$ é monotônica, o que nos dá uma complexidade $O(\lg{n})$ para cada calculo do valor de $j$. É perceptível que o número de iterações (número de saltos) é da ordem de $\sqrt{k}$. Por fim, implementando desta forma temos uma solução $O(\sqrt{k} \cdot \lg{n})$.

Ainda é importante salientar que não precisamos usar a busca binária para achar os valores de $j$, isso pode ser feito em $O(1)$, o que reduz o tempo da solução para $O(\sqrt{k})$.

Testes

Entrada

1000000000 500000000

1000000000 1000000000

Saída

294383241290555707

177532965887639372

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License