[AtCoder] ABC 172 D – Sum of Divisors
問題
方針
エラトステネスの篩のような考え方で約数を数え上げます。
\( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません