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で紹介したスターリングの公式を使うと、1013 桁の数になることが分かります。とても計算できる大きさではありません。
入力例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の累乗について、具体的に計算してみましょう。
| K | 最小のN! | 2を素因数にもつ数 |
| 21 | 2! | 2が1個 |
| 22 | 4! | 2が1個、4が2個 |
| 23 | 4! | ↑に同じ |
| 24 | 6! | 2、6が1個、4が2個 |
| 25 | 8! | 2、6が1個、4が2個、8が3個 |
| 26 | 8! | ↑に同じ |
| 27 | 8! | ↑に同じ |
| 28 | 10! | 2、6、10が1個、4が2個、8が3個 |
| 29 | 12! | 2、6、10が1個、4、12が2個、8が3個 |
| 210 | 12! | ↑に同じ |
| 211 | 14! | 2、6、10、14が1個、4が2個、8が3個 |
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, …, 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 の問題を紹介していきます。
