Sum of Divisors [AtCoder Beginner Contest 172 D]

https://atcoder.jp/contests/abc172/tasks/abc172_d

前提知識

• エラトステネスの篩

解説

https://atcoder.jp/contests/abc172/submissions/14777943

[1,K]の約数の個数を効率的に数え上げる必要がある。
以下のことを知っているとエラトステネスの篩が思いつくだろう。
- 約数の個数は、素因数分解ができていれば、各素因数の個数+1の総積と等しくなる
- 区間の素因数分解はエラトステネスの篩っぽいアルゴリズムが使える

エラトステネスの篩

もし知らない場合はどこかで勉強してこよう。
2,3,4,5,6,...と数を見ていくときに割れるだけ割るような処理を追加して、
割れるだけ割るような処理をするときに割った個数をカウントしておくと、
その個数がその素因数の個数となるので、個数+1を組合せに掛け合わせていく。
f[x] := xの約数の個数
こういう風に配列を用意しておくと、問題に寄っていいかもしれない。
これで最後に作った配列fを使って問題に書いてある通りに計算すれば答え。
計算量はO(NlogN)でN=10⁷なので、だいぶギリギリ。
C++じゃないと通らないんじゃないかなと思うから、たぶん想定解じゃない。

【別解】chokudaiさんツイート

(8) chokudai(高橋 直大)🌸🍆さんはTwitterを使っています 「一応ぷち解説。10万ごとくらいの答えを予め配列かなにかに入れておけば、そこから先を差分計算してあげれば答えが高速に求まるよ、みたいな感じ。」 / Twitter
なるほど、yukicoderでそんな問題見たな…
これは、埋め込みテク。
これは例えば、1～10000の答えを求めたいとしたときに、1,100,200,300,...の答えを事前計算して埋め込んでおく。
すると、例えば250の答えが知りたいときは、200までの答え+201～250の答えを答えればいい。
200までの答えは事前に計算して埋め込んでいるのでO(1)で、別途201～250の差分だけ計算すればいいので、計算が軽くなる。
埋め込み間隔をsqrt(N)くらいにしておけば、差分計算分もsqrt(N)個くらいになるので、実質Nがsqrt(N)と考えて解けるってやつ。

int N;
int val[10101010], f[10101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 1, N + 1) val[i] = i, f[i] = 1;
    rep(p, 2, N + 1) for (int x = p; x <= N; x += p) {
        int c = 0;
        while (val[x] % p == 0) val[x] /= p, c++;
        f[x] *= c + 1;
    }

    ll ans = 0;
    rep(i, 1, N + 1) ans += 1LL * i * f[i];
    cout << ans << endl;
}