数カ月ぶりに参加した割に健闘したと言って良いと思う。最近、数学の勉強を頑張ってるのでDみたいなのが解けたのは良かった。
D - AABCC
https://atcoder.jp/contests/abc300/submissions/41048006
まず、問題文を見た瞬間素数列挙したくなる。ただし、素数列挙（エラトステネスの篩）の計算量は であり
のままでは間に合わないので、どうすれば計算量が落ちるのか考えなければならない。ここで、もう一度問題文を読んだとき abc が昇順固定なのが怪しいと思った。例えば a=2, b=3 のとき c は最大で
なので、なるほど
までの素数列挙で十分なのだなと気づいた。次に
を全列挙するフェーズだが、愚直に処理すると
これまた間に合わないので困った。計算結果がN以下かどうか調べないといけないので、K個の素数のうち3つ選ぶ
など組み合わせ的な手法も使えない。ここは結構悩んだが、発散の速い数値つまり
を優先して計算し N を超えたら枝刈りする方針で結構計算量が落ちるんじゃないかというアイデアを思いつく。正確な計算量は不明だが、かなり計算量が落ちそうなので実装して試したら十分高速に処理できたので良さそうという気持ちになり提出しようとした。が、サンプル3の出力が合わない。基本的に単純な全列挙をしてるので答えが合わないというのは意味不明すぎて非常に困った。もう駄目か～と諦めかけた時に「最大
の数値を5回も乗算してるってことは計算途中でオーバーフローしてないか？」ということに気づく。BOOSTの多倍長整数を使ったコードに書き換えたところサンプル3の出力が一致した。コンテスト終了間際に提出して何とかACできた。
