以下にはABC152のE問題 Flatten のネタバレが含まれます。
この問題は多倍長整数を使用できる言語であれば愚直解が通ります。Haskellで書かれた愚直解のコードは、例えばSubmission #9632460 - AtCoder Beginner Contest 152が簡潔で読みやすいです。
foldr lcm 1 a
の部分は、回「ビットの整数とビットの整数の最大公約数(高々ビット)を求め、ビットの整数をそれで割り、その結果とビットの整数を掛け合わせる」という計算を行うはずです。ビットの整数とビットの整数の最大公約数をユークリッドの互除法で求めると、多倍長除算は長除法(筆算)を用いるとして、時間計算量がとなります。
残りの部分は、取るに足らない計算量です。
制約はなので、愚直解は雑な概算でΟの中がになります。時間制限は2秒であり、サイクル以上のCPU時間があるので、これは余裕で間に合います。実際、多くのHaskellでの愚直解の提出は、200msから300msくらいで動作しています。
C++標準には残念ながら多倍長整数がありません。 しかし、この問題に限っては位取り記数法を用いた多倍長整数を使う必要はありません。 掛け算せず、因数*1の列として保持すればよいです。
それを利用した解法の提出が以下です。
Submission #9637654 - AtCoder Beginner Contest 152
全然間に合っていません。実際、この解法の時間計算量はであり、愚直解より20倍ほど遅いことがわかります。つまり、3倍程度間に合いません。
手元で作った雑な最大ケースでは間に合ったため大丈夫だろうと思っていたのですが、よくよく考えると真の最大ケースは、「個の未満の相異なる素数」です(テストケースの実行時間から推察すると、おそらくmax_02がこれです)。
そのケースを手元で動かした場合からの概算だと、ジャッジサーバーでは6秒くらいかかりそうだという感じだったので、いろいろな計算が大体合います。
そこで、自作の高速化したgcd
関数を使えば間に合うのではないかと考えました。
以下は、最大公約数をもっと高速に求める(その4) - よーるで示した高速なgcd
関数を、入力がを超えない場合に特化したものです。
std::uint64_t gcd_impl( std::uint64_t n, std::uint64_t m ) { constexpr std::uint64_t K = 5; if( m == 0 ) { return n; } for( ; n / 64 < m; ) { std::uint64_t t = n - m; std::uint64_t s = n - m * K; bool q = t < m; bool p = t < m * K; n = q ? m : t; m = q ? t : m; if( m == 0 ) { return n; } n = p ? n : s; } return ::gcd_impl( m, n % m ); } std::uint64_t gcd( std::uint64_t n, std::uint64_t m ) { return n > m ? ::gcd_impl( n, m ) : ::gcd_impl( m, n ); }
また、64 bit整数にはが収まるので、因数を3つまとめて保持することにより、高速化を図ります。これをおしすすめると愚直解になるわけです。
ところで、このgcd
関数は、g++でコンパイルすると、mov
命令を減らしたいのかわかりませんが低速なcmova
命令にコンパイルされてしまいます(最大公約数をもっと高速に求める(その2)【cmova命令は遅い】 - よーる)。clang++だとそのようなことはないため、clang++で提出します。
Submission #9639909 - AtCoder Beginner Contest 152
1825msというぎりぎりですが、通すことができました。
かかった時間から推察すると、自作のgcd
関数は一回当たり300サイクル程度で動作しているということがわかりました。
*1:素因数ではありません