ABC052 C問題（Factors of Factorial）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）052 C問題をC++で解いてみました。ABC052は、2017年1月15日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 Factors of Factorial（Difficulty : 967）

問題の詳細は、リンク先をご覧ください。

ABC052 C問題 Factors of Factorial

素因数分解の結果を累積して解を求めます。AtCoder Problems による Difficulty は 967 でした。

解答案

整数 $N$ を素数 $p_1, p_2, … p_k$ で素因数分解します。

$$N = p_1^{r_1} \times p_2^{r_2} \times \cdots \times p_k^{r_k}$$

$N$ の約数は、$p_1$ を 0 から $r_1$ 個まで含みます。それぞれの素因数についても同様です。このため、$N$ の約数の個数は、

$$(r_1 + 1) \times (r_2 + 1) \times \cdots \times (r_k + 1)$$

となります。

C++ プログラム例（ABC052C）

$1$ から $N$ までの整数を素因数分解して、素因数の個数を累積して $N!$ の素因数分解の結果を得ることができます。

• 素因数分解は、自前で準備した関数 prime_factor を使いました（9ー24行目）。
  • 関数 prime_factor は、素因数分解の結果（素数と累乗）を組とする map として返します。
• 素因数の個数を累積して $N!$ の約数の個数を計算します（31－43行目）。大きな値となるため問題の指示に従い、$10^9 + 7$ で割った余りを出力します。この計算には、ACL（AtCoder Library）の modint を使いました。

以下が、C++プログラムです。

#include <atcoder/modint>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;

typedef unsigned long long int ull;
typedef modint1000000007 mint;

map<ull, ull> prime_factor(ull n)
{
	map<ull, ull> result;

	for (ull i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			++result[i];
			n /= i;
		}
	}
	if (n != 1) {
		result[n] = 1;
	}

	return result;
}

int main()
{
	int n;
	cin >> n;

	map<ull, ull> d;
	for (int i = 1; i <= n; ++i) {
		map<ull, ull> r;
		r = prime_factor((ull)i);
		for (auto e : r) {
			d[e.first] += e.second;
		}
	}

	mint result = (mint)1;
	for (auto e : d) {
		result *= e.second + 1;
	}

	cout << result.val() << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

最後に

整数の約数については、ABC383D問題（解説記事）で扱いました。類題として、この問題を解説しました。

引き続き ABC の問題を紹介していきます。