ABC280 D問題（Factorial and Multiple）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）280 のD問題をC++とPythonで解いてみました。ABC280は、2022年12月3日21:00に実施されました。

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

D問題 Factorial and Multiple（Difficulty : 880）

問題はリンク先をご覧ください。

ABC280 D問題 Factorial and Multiple

与えられた数字を素因数分解をして、解答を求めます。AtCoder Problems による Difficulty は、880 でした。

解答案

素朴に考えると、K の倍数となるような N! を計算すればよいと思うかもしれません。ただし、N! は非常に速く大きくなります。このため階乗の記号が ! になっているという人もいます。

例えば、入力例2にある 123456789011 の解答は、123456789011 の階乗になりますが、これは、Project Euler 問題20で紹介したスターリングの公式を使うと、10¹³ 桁の数になることが分かります。とても計算できる大きさではありません。

入力例2の 123456789011 が素数であることに気づくと、素因数分解を使うことが分かります。

素因数分解を行う関数

素因数分解は、Project Euler 問題3で考察しました。$\sqrt{n}$ まで調べれば効率良く素因数分解ができることが分かりました。

素因数分解は関数として独立させることにします。関数名や戻り値に map を使うことも含めて、「蟻本」（「プログラミングコンテストチャレンジブック」第2版 秋葉拓哉、岩田陽一、北川宣稔著、マイナビ 2012年）を参考にしました。

以下が関数 prime_factor の実装例です。

typedef unsigned long long int ull;

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;
}

次に考えること

問題に掲載されている3つの入力例と出力例（解答）を振り返ります。

• 入力例1　$30=2\times 3\times 5$ の解答は、 $5!=120$
• 入力例2　$123456789011$ は素数、解答は、$123456789011!$
• 入力例3　$28=2^2\times 7$ の解答は、$7!=5040$

この3例だけみると、一番大きな素因数が解答になると勘違いするかもしれませんが、それは間違っています。

• 入力例4　$12=2^2\times 3$ の解答は、$3!=6$ ではなく、$4!=24$ になる。

計算が簡単な2の累乗について、具体的に計算してみましょう。

4は、2を2個素因数に持ち、8は、2を3個素因数に持つため、K が増えても N! が増えない場合があることが分かります。

この問題は、特定の素因数をいくつ含むかカウントする問題となります。式で具体的に記します。

$K=b_1^{p_1}{b}_2^{p_2}\cdots b_m^{p_m}$ と素因数分解できたとします。この場合に、素因数 $b_i$ を $p_i$ 個以上含む最小の $N_i!$ を求める問題となります。

方針

問題を解く方針を書きだします。

• K を読み込む。
• K を素因数分解する。$K=b_1^{p_1}{b}_2^{p_2}\cdots b_m^{p_m}$
• それぞれの $m$ に対して、以下を求める。
  • 素因数 $b_i$ を $p_i$ 個以上含む最小の $N_i!$ を求める。
• 最大の $N_i(i=1,2,\dots ,m)$ を出力する。

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

素因数分解をして得られた $b_i^{p_i}$ に対して、$b_i\times n$ が素因数 $b_i$ をいくつ 含むか求めて加えていき、$p_i$ 個以上含むような最小の $(b_i\times n)!$ を求めています。

以下が、C++の実装例です。

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

typedef unsigned long long int ull;

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()
{
	ull k;
	cin >> k;

	ull result = 1;
	map<ull, ull> m;

	m = prime_factor(k);
	for (auto it = m.begin(); it != m.end(); ++it) {
		ull b = (*it).first;
		ull p = (*it).second;
		ull n = 1;
		ull p_t = 1;
		while (p_t < p) {
			++n;
			++p_t;
			ull n_t = n;
			while (n_t % b == 0) {
				++p_t;
				n_t /= b;
			}
		}
		result = max(result, b * n);
	}

	cout << result << endl;

	return 0;
}

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

Python プログラム例（ABC280D）

素因数分解する関数は、defaultdict を返しています。基本的に C++ をそのまま置き換えたプログラムです。

"""AtCoder Beginner Contest 280 D"""
from collections import defaultdict


def prime_factor(n):
    factor = defaultdict(int)
    i = 2
    while i * i <= n:
        while n % i == 0:
            factor[i] += 1
            n //= i
        i += 1
    if n != 1:
        factor[n] = 1
    return factor


k = int(input())
result = 1
m = prime_factor(k)
for b, p in m.items():
    n = 1
    p_t = 1
    while p_t < p:
        n += 1
        p_t += 1
        n_t = n
        while n_t % b == 0:
            p_t += 1
            n_t //= b
    result = max(result, b * n)

print(result)

こちらも「AC」と判定されました。

最後に

この問題を解くときには、2の累乗の場合を手計算して構造を把握しました。構造が把握できない場合には、簡単な場合に手計算することが有効であることが分かりました。

ABC280は、B問題とC問題は取り組みやすいと感じました。特にC問題は簡単に感じました。一方、D問題は、手計算で構造を把握して時間内に解くことができました。

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