\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-force>}}\)

• Với mỗi số \(n\) trong đoạn \([l, r]\)

Ta tính tổng ước của chúng là \(divsum[n] = \underset{d | n}{\Sigma} d\)

Ta sẽ cộng vào kết quả giá trị \(f[n] = |n - (divsum[n] - n)|\)

\(\color{orange}{\text{Hint 2 <Precalculation>}}\)

• Thay vì từ mỗi số ta tìm ước tì với mỗi số ta tăng giá trị các bội của nó lên

Ta cần tính đoạn \([l, r]\) nên không cần xét các số lớn hơn

Duyệt lần lượt các số \(d\) từ \(1 \rightarrow r\)

Ta tăng giá trị các bội \(x\) của \(d\) lên \(d\)

\(\color{green}{\text{Preference AC Code }}\): Precalculation

\(^{^{\color{purple}{\text{Complexity : }} O(n \log n)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int main()
{
    int l, r;
    cin >> l >> r;

    vector<int> divsum(r + 1, 1);
    divsum[0] = 0;
    for (int i = 2; i <= r; ++i)
        for (int j = i; j <= r; j += i)
            divsum[j] += i;

    ll res = 0;
    for (int n = l; n <= r; ++n)
        res += abs(2 * n - divsum[n]);

    cout << res;
    return 0;
}