コンテスト中AC:A〜D
D - Index Trio
を変形すると、
となります。
を固定すると、
は
の約数の組に限定されます。
よって、について、
である約数
についてのみ調べれば良く、各
について、
で全探索できます。
計算量は、の最大値を
として、
となり、間に合うか微妙なところですが大丈夫でした。
となる組が何通りあるかですが、
を
に出現する
の個数とすると、
となります。
これは、となる全ての
に対して、
となる
と組を作ることができるためです。
である
について組を計算するわけですが、
である場合、組の順序を入れ替えると別の組になるので、2倍します。
逆に、の場合は入れ替えてできる組は同じなので、2倍しません。
提出コード Submission #31196140 - Monoxer Programming Contest 2022(AtCoder Beginner Contest 249)
なお、計算量を落とすことが可能です。
の全てについて、エラトステネスの篩と同じ方法で、試し割り不要で約数が記録された二次元配列を得ることが可能です。
計算量はとなり、二次元配列のサイズも同様に
となると考えられます。
組の計算にかかる計算量ですが、
上記に高度合成数の言及がありますが、ある整数以下の約数の個数が最大となるのが高度合成数です。
が全て
以下の高度合成数
であった場合が最悪となり、
です。
上記によれば以下の高度合成数の約数の個数は160個なので、問題ないです。
Submission #31257209 - Monoxer Programming Contest 2022(AtCoder Beginner Contest 249)