AtCoder Beginner Contest 172, D : Sum of Divisors

問題文

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

問題概要

　正整数 $X$ について，関数 $f$ を

• $f( X ) = $ $X$ の約数の個数

とする．
　正整数 $N$ が与えられるので，$$\sum_{ K = 1 }^{ N } K \times f( K )$$ を求めよ

制約

　$1 \leq N \leq 10^7$

解法

　それぞれの整数について $f$ の値が分かれば，後は for ループで $\sum$ を計算するだけで答えが求まります．「$X$ の約数の個数」というのはちょっと言い換えると「$X$ が倍数になるような整数の数」です．そこで，大きめの配列を用意して，Eratosthenes の篩のような気持ちで各整数の倍数の添字のところをインクリメントしていくと，$f$ の値が求まります．
　この処理には，$1$ の倍数を篩うのに $N$ 回程度，$2$ の倍数を篩うのに $\frac N 2$ 回程度，$3$ の倍数を篩うのに $\frac N 3$ 回程度……という風に計算量がかかります．$$\sum_{ i = 1 }^{ N } \frac N i = N \sum_{ i = 1 }^{ N } \frac 1 i$$ で，$\sum_{ i = 1 }^{ N } \frac 1 i$ とは調和数です．調和数の発散速度は項数 $n$ について $O( \log n )$ 程度なので，上記の式の発散速度は $O( N \log N )$ ということになり，やや厳し目ですが間に合います．

コード

int main()
{
	IN( int, N );

	static int divisors[ 1 << 24 ];
	REP( i, 1, 1 << 24 )
	{
		for ( int j = 1; i * j <= N; ++j )
		{
			++divisors[ i * j ];
		}
	}

	LL res = 0;
	REP( i, 1, N + 1 )
	{
		res += LL( i ) * divisors[i];
	}
	cout << res << endl;

	return 0;
}