Lời giải: Tổng các ước số

Phân tích

Thay vì duyệt từng số \(i\) và phân tích ước, ta đếm số lần \(d\) xuất hiện. Số \(d\) là ước của các số \(d, 2d, 3d, \dots\) trong đoạn \([1, N]\). Có \(\lfloor N/d \rfloor\) số như vậy. Tổng: \(\sum_{d=1}^{N} d \times \lfloor N/d \rfloor\). Duyệt \(d\) từ 1 đến \(N\), cộng dồn. Độ phức tạp: \(O(N)\).

Code mẫu C++

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

int main() {
    int N;
    cin >> N;
    long long ans = 0;
    for (int d = 1; d <= N; d++) {
        long long cnt = N / d;
        ans = (ans + (long long)d * cnt) % MOD;
    }
    cout << ans << endl;
    return 0;
}