Ao nos depararmos com a necessidade de calcular somatórios da forma:

Fundamentação Teórica

A chave para essa otimização reside na observação de que a função $y = \lfloor \frac{n}{x} \rfloor$ assume a forma de uma "escada". Isso significa que existem intervalos contínuos de valores de $x$ para os quais o resultado da divisão inteira é exatamente o mesmo.

Se definirmos o conjunto de todos os valores únicos assmuidos por $\lfloor \frac{n}{x} \rfloor$ como $S = \left\{ \lfloor \frac{n}{x} \rfloor \mid x \in [1, n] \cap \mathbb{N} \right\}$, cada elemento $d \in S$ corresponderá a um intervalo $[l, r]$ onde, para todo $x \in [l, r]$, temos $\lfloor \frac{n}{x} \rfloor = d$.

Com isso, podemos reescrever o somatório original agrupando os termos:

Propriedades dos Intervalos

Limite Superior de Blocos

O tamanho do conjunto $S$ é estritamente limitado por:

• Para $i \le \sqrt{n}$, existem no máximo $\sqrt{n}$ valores possíveis para $i$, logo, no máximo $\sqrt{n}$ resultados distintos para $\lfloor \frac{n}{i} \rfloor$.
• Para $i > \sqrt{n}$, temos que $\lfloor \frac{n}{i} \rfloor \le \frac{n}{i} < \sqrt{n}$, o que também gera no máximo $\sqrt{n}$ valores distintos.

Somando ambos os casos, concluímos que o número total de blocos não excede $2\sqrt{n}$.

Determinação dos Limites $l$ e $r$

Para um determinado valor $d = \lfloor \frac{n}{l} \rfloor$, o limite superior $r$ do intervalo atual pode ser calculado diretamente como:

Implementação Prática

Considere as funções $f(x) = x + 8$ e $g(x) = x^2 + 5x + 6$. Queremos calcular o somatório para $n = 1000$.

Abaixo, apresentamos uma implementação em C++ utilizando somas prefixadas:

#include <iostream>
#include <vector>

using namespace std;

int computeF(int val) { return val + 8; }
int computeG(int val) { return val * val + 5 * val + 6; }

int main() {
    int limit = 1000;
    long long totalSum = 0;
    vector<long long> prefixSum(limit + 1, 0);

    for (int i = 1; i <= limit; ++i) {
        prefixSum[i] = prefixSum[i - 1] + computeF(i);
    }

    for (int left = 1, right; left <= limit; left = right + 1) {
        int quotient = limit / left;
        right = limit / quotient;
        long long blockFSum = prefixSum[right] - prefixSum[left - 1];
        totalSum += blockFSum * computeG(quotient);
    }

    cout << totalSum << endl;
    return 0;
}

O resultado esperado para esta entrada é 27314136.

Para cenários onde $n$ é extremamente grande (por exemplo, $10^{15}$), não podemos alocar um array de somas prefixadas. Nesses casos, se $f(x)$ for uma função polinomial simples, podemos calcular a soma do intervalo $[l, r]$ analiticamente. O exemplo abaixo demonstra essa abordagem para $n = 10^{15}$ com aritmética modular ($10^9 + 7$):

#include <iostream>
#include <algorithm>

using namespace std;

const long long MOD = 1e9 + 7;
const long long INV2 = 500000004; // Inverso modular de 2

long long computeG(long long val) {
    return (val % MOD * (val % MOD) % MOD + 5 * (val % MOD) % MOD + 6) % MOD;
}

long long sumF(long long l, long long r) {
    long long count = (r - l + 1) % MOD;
    long long sumVals = ((l % MOD) + (r % MOD)) % MOD * count % MOD * INV2 % MOD;
    long long sumConst = 8 * count % MOD;
    return (sumVals + sumConst) % MOD;
}

int main() {
    long long limit = 1e15;
    long long totalSum = 0;

    for (long long left = 1, right; left <= limit; left = right + 1) {
        long long quotient = limit / left;
        right = min(limit, limit / quotient);
        
        long long currentBlock = sumF(left, right) * computeG(quotient) % MOD;
        totalSum = (totalSum + currentBlock) % MOD;
    }

    cout << totalSum << endl;
    return 0;
}

O resultado modular esperado é 990965906.

Variações e Aplicações

Divisão com Arredondamento para Cima

Se o problema exigir o cálculo de $\lceil \frac{n}{i} \rceil$, podemos utilizar a identidade matemática:

Um problema clássico envolve calcular a soma dos restos da divisão de $k$ por todos os inteiros de $1$ a $n$:

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    long long limit, divisorVal;
    cin >> limit >> divisorVal;
    
    long long totalSum = limit * divisorVal;
    
    for (long long left = 1, right; left <= limit; left = right + 1) {
        if (divisorVal / left == 0) break;
        right = min(divisorVal / (divisorVal / left), limit);
        
        long long count = right - left + 1;
        // Prevenção contra overflow em long long
        long long arithmeticSum = (count % 2 == 0) ? (left + right) * (count / 2) : ((left + right) / 2) * count;
        totalSum -= arithmeticSum * (divisorVal / left);
    }
    
    cout << totalSum << endl;
    return 0;
}

Soma dos Divisores em um Intervalo

Para calcular a soma de todos os divisores dos números em um intervalo $[X, Y]$, podemos definir uma função auxiliar $G(x)$ que retorna a soma dos divisores de $1$ até $x$. A resposta final será $G(Y) - G(X - 1)$.

A função $G(x)$ pode ser reescrita contando quantas vezes cada número $i$ aparece como divisor no intervalo $[1, x]$, o que ocorre $\lfloor \frac{x}{i} \rfloor$ vezes:

#include <iostream>

using namespace std;

long long calculateDivisorSum(long long x) {
    if (x <= 0) return 0;
    long long result = 0;
    
    for (long long left = 1, right; left <= x; left = right + 1) {
        long long quotient = x / left;
        right = x / quotient;
        
        long long count = right - left + 1;
        long long arithmeticSum = (count % 2 == 0) ? (left + right) * (count / 2) : ((left + right) / 2) * count;
        result += arithmeticSum * quotient;
    }
    
    return result;
}

int main() {
    long long lowerBound, upperBound;
    cin >> lowerBound >> upperBound;
    
    cout << calculateDivisorSum(upperBound) - calculateDivisorSum(lowerBound - 1) << endl;
    return 0;
}