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
Discuta o problema
Muito interessante.
Só o $O(\sqrt{k} \cdot \lg{n})$ funcionou aí? Achei que deveria funcionar mas acabei de tomar TLE assim.
Sim, funcionou! Com $O(\sqrt{k} \cdot \lg{n})$ passei com ~550ms, escovei alguns bits e consegui ~300ms. Já com $O(\sqrt{k})$ o tempo não melhorou tanto, passou com 140ms.
Muito estranho. O tempo de execução no meu computador é muito baixo:
Ninguém tá tendo problema de TLE nesse problema além de mim?
Tiago, tenta submeter em G++ em vez de C++. Embora o C++ seja mais "confiável", ele é mais lento, acho … Eu submeti meu código $O(\sqrt{k} \cdot \lg{n})$ e teve uma diferença de ~100ms para C++ (pode sido apenas o tráfego no servidor também, não sei). Mais uma coisa lenta são as operações com inteiros de 64 bits, então é bom usá-los apenas quando necessário. Outra coisa, sua busca binária está recursiva? O meu código está recursivo, e passa, mas derrepente isso pode melhorar o tempo!
Funcionou com G++! Esse PKU é muito estranho.
Obrigado!
Nossa, comigo foi exatamente o contrário!
Fiz a solução $\mathcal O (\sqrt k)$ e tomei TLE quando submeti com o G++ por engano. Resubmeti a mesma com C++ e passou em 200MS.
Hehe! Comigo G++ foi mais rápido, 157ms contra 235ms com C++.