📝

ABC 280 D - Factorial and Multiple の解説の解説

2022/12/05に公開

Python

AtCoder

abc

tech

わからされたABC280のDについて

素因数分解の性質についてわからせられた良い問題でした

解説

……😇
わからん。わからせて。

公式解説｢の｣解説

おれみたく、茶色の500程度だと解説を理解できないかも。
でも大丈夫!けんちょんさんやフレンズさんらの解説はわかりやすいね!

とある素数で割れる数は、素数 $\times$ 整数倍で求められる。
なので、素因数 $\times$ 素因数の指数が解 ｢ではない｣ ということがわかったよ!!

$8!$ のケースを考える

$8!=1\times2\times3\times4\times5\times6\times7\times8$
$8!=1\times2\times3\times(2\times2)\times5\times(2\times3)\times7\times(2\times2\times2)$
となり、2は7回も出てきている。
つまり $K=128(2^7)$ であれば8が解となる
どうやってこの8を算出するかを考える必要が出てくる

愚直に数える

階乗にて素因数の数が出るのは、｢素因数の倍数｣のときのみ。
つまり、素因数の倍数をチェックして何回出てきたのかを数えれば良い。
数える必要のある素因数の数は、最大でも素因数の指数値( $2^n$ ならn)個しか無いので時間はかからない。
よく出来てんなぁ。

# x = 素因数、y = 素因数の指数
# x が y 回出る階乗を求める
def calc_factorial_num(x,y):
    cnt=0
    for i in range(x, x ** y + 1, x):
        n = i
        while n % x == 0:
            n //= x
            cnt += 1
        if cnt >= y:
            return i

ABC280 D振り返り

わからされたこと

$K=P_1^{e_1} \times P_2^{e_1} \times \dots \times P_n^{e_n}$ であれば、Kは $P_x^{e_x}$ の倍数である
この性質は日頃生活では出て来ないけれど、類似の問題は今後見かけそうなので覚えておこう!

良かったこと

解けない問題であっても、1時間以上取り組める集中力を持ってるんだなぁと実感できた。
ABCが簡単だったのもあるけれど、自分でもびっくりするくらい集中できた。
解けそうだけれど、やっぱり解けない、丁度いい難易度だったのが良かったのかも?
次回も頑張るぞー!

本番中に考えたこと

倍数を考えることから、Kを素因数分解するのは間違えない
$210=2\times3\times5\times7$ なので、出現素数がすべて1なら素因数分解の最大値
素因数分解の数字を用い、出現数がすべて1となるように変換できれば解になる

方針

$2\times2\times2\times3\times3\times3\times5\times5$ であれば、 $2\times2\times3\times3\times5\times(2\times3\times5)$ と変形できる!

前半部分を組み合わせ、最小の数字となる組み合わせを見つける
後半部分の最大値と比較し、小さい方が解となる
よし!いい感じに方針まとまった!!
これは4完いけるんじゃない?

1の実装で詰まる

$2\times2\times3\times3\times5$ で組み合わせて最小値を作るには……。
良うわからんけれど、小さい方から積算すればええのかな?

$2\times2\times5=20,3\times3=9$ で20
$2\times5=10,2\times3\times3=18$ で18
……違うっぽいな。
なら両端から組み合わせるのか?
いや、1つ余った場合の処理どうすればいいんだ?
……これ単純には求められないんじゃないか?

ざっくり思い浮かぶ単純に求められなさそうなケース

$2\times2\times2\times2\times99991$ のようにでかい素数が出てきた場合
- 99991が解なのは明白
$2^{500} \times 3^{500}$ のように出現する数が多い場合
- 1000ある場合は、2～1000個の選び方を全通り試し最小値を見つける
- $n=2$ のケースなら
  $_{1000} C_2 + _{998} C_2 + \dots + _{4} C_2 + _{2} C_2$
  なんか違う気もするが、こうなるのか?
  これを2から1000通りのパターンを全部試して最小値求めるとか2秒じゃ無理だ

どうすりゃいいの!!
となり、4完はお預け😭