誤読がつらすぎる。ABの2完。かなり解くのが遅くなってしまった。 Bが解けたので死ぬほど爆死したということではない。パフォーマンスは爆死していると思うけど、 正直なところ今の実力はこのくらいなんじゃないかなと感じてきた。
皿に $1$ つだけ置く場合を考えると、大きいものだけ置けばいい。 $2$ つ置くものはそれより小さいもので、これは小さいものと大きいもののペアで作ればいい。 この操作は昇順ソートした配列を用意すると簡単に処理できる。
今思えばそんなに時間をかけるものではない。 自分は総積の部分を読んでいたが意味を履き違えた。 これをすべての約数について何回割り切れるかを足し上げるものだと思っていた。 しかし、総積と指定する場合、割り切れないものに対しても足し上げることができるので答えそのものが 違ってきてしまう。
まず約数についてすべて足し上げるとなる場合、答えに調和数などがでてきてしまったり、 そもそもすべての合成数に使えなかったりしていたのでさすがに $B \leq 10^{18}$ について解けないだろとなった。
実際に小さい $B$ でシミュレーションしてみても(今回のサンプルはかなり役に立った)、全然違う答えになって しまったので、これは問題を読み違えている可能性が高いという結論に至った。ここまでで80分くらい使ってる気がする。
総積となると急に答えは求まりやすくなる。ある素因数の素数 $p$ についてすべて掛けたときに何乗になるかということだが、
まず $A$ についての素因数の素数 $p_k$ が何回割り切れるかを $c_{p_k}$ と置く。 その際、素数 $p_i$ について何乗になるか求めると、
$$ \frac{\prod_{k}{(c_{p_k} \times B + 1)}}{c_{p_i} \times B + 1} \times \frac{(c_{p_i} \times B + 1) \times (c_{p_i} \times B)}{2} $$
となることがわかる。そしてその素数について何回割り切れるかを計算すると $2 \times c_{p_i}$ で割ることになるわけである(しかも切り捨てで)。 各素数について何回割り切れるか計算してその最小値を出せれば答えになるが、Modulo演算なので最小値は求められない。 しかし、この式は、 $2 \times c_{p_i}$ で割ることでかなり単純になる。
$$ \frac{\prod_{k}{(c_{p_k} \times B + 1)} \times B}{2} $$
となるので実は $p_i$ によらない。したがって最小値を求めずともこの値を計算すればいい。
しかし、この $2$ は切り捨てで割らないといけないので、Modulo演算ではおかしくなる。 このとき、他の計算を $(mod \times 2)$ で計算しておくと、切り捨て計算ができるようになり、AC する。
脳内にあったことを全部書いたが、ちょっと何書いてるかあとから読んだら何もわからない気がするｗ
今回はかなりパフォーマンスもひどいとは思うが、個人的には充実した内容になったと思う。 そこまでテンパってもいなかったし、考察フェーズも悪くなかったのではと思う。こういう誤読は普通に実力だなぁとは思った。
ちゃんと答えに導けたのでそこはえらい。あとはこういうのを速解きできればCDの考察にも時間を回せるし、 まだまだ伸びしろがあるなと感じた。解けたことは大きい。
(2023/10/15 23:28)