📝

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

2022/12/05に公開約2,300字

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

https://atcoder.jp/contests/abc280/tasks/abc280_d
素因数分解の性質についてわからせられた良い問題でした

解説

https://atcoder.jp/contests/abc280/editorial/5330
……😇
わからん。わからせて。

公式解説「の」解説

おれみたく、茶色の500程度だと解説を理解できないかも。
でも大丈夫!けんちょんさんやフレンズさんらの解説はわかりやすいね!
https://drken1215.hatenablog.com/entry/2022/12/05/160400

https://twitter.com/kyopro_friends/status/1599038305236307969?conversation=none

とある素数で割れる数は、素数\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)と変形できる!

  1. 前半部分を組み合わせ、最小の数字となる組み合わせを見つける
  2. 後半部分の最大値と比較し、小さい方が解となる
    よし!いい感じに方針まとまった!!
    これは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完はお預け😭

Discussion

ログインするとコメントできます