[AtCoder] ABC 172 D – Sum of Divisors

2020年12月14日

問題

方針

エラトステネスの篩のような考え方で約数を数え上げます。

\( i \) の約数の個数 \( a(i)\) とすると、\( 1 \leq ij \leq 10^7 \) を満たす、\( 1 \leq i \leq 10^7 , 1 \leq j \leq 10^7\) に対して \( a(ij) \) に \( 1 \) を加算していくことで求めることができます。

 コード

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

const int M = 10000001;
ll a[M];
int main() {
    int N;
    cin >> N;
    fill(a, a + M, 1);
    for (ll i = 2; i < M; i++) {
        for (ll j = 1; i * j < M; j++) {
            a[i * j]++;
        }
    }
    ll ans = 0;
    for (ll i = 1; i <= N; i++) {
        ans += i * a[i];
    }
    cout << ans << "\n";
    return 0;
}