アルゴリズムと数学 演習問題集 042 - Sum of Divisors

記事概要

アルゴリズムと数学 演習問題集 042 - Sum of Divisorsのとりあえず動くコードと説明．https://atcoder.jp/contests/math-and-algorithm/tasks/abc172_d

注意

アルゴリズム初心者が書いています．時間内の動作は確認してますが、必ずしも最適解ではないです．

とりあえずコード

042_main.cpp

///////////////////////////
// 042 - Sum of Divisors //
///////////////////////////

#include <iostream>
#include <vector>

using ll = long long int;

using std::vector;

int main(void) 
{
	//-------------------------------- 入力 --------------------------------//
	int N;
	std::cin >> N;

	//-------------------------------- 計算 --------------------------------//
	vector<ll> divisor_num(N + 1, 1);

	// divisor_num[i]にiの約数の個数を格納する
	for (int i = 2; i <= N; ++i) {
		for (int j = i; j <= N; j += i) {
			divisor_num[j] += 1;
		}
	}

	// 出力値を計算
	ll ans = 0;
	for (int i = 1; i <= N; ++i) {
		ans += i * divisor_num[i];
	}

	//-------------------------------- 出力 --------------------------------//
	std::cout << ans << std::endl;
}

説明

この問題は、整数nの約数の個数の計算をN回繰り返して答えを計算すると時間が足らなくなります．
整数nの約数を求めるのではなく、1～Nまでの内nを約数として持つものはどれかという考えで計算していかなければなりません．

例えばn=2のときであれば、nを約数としてもつ値は2つおきに現れます．同じようにn=3であれば3つおき現れます．

この性質を利用して、配列divisor_numをn間隔で1増やす操作を$n:1～N$繰り返します．

これによりdivisor_num[i]にはiの約数の個数が格納されているので、最後に$\sum^N_{k=1}k \times divisorNum[k]$を計算すれば、求める答えが得られます．