https://lpha-z.hatenablog.com/entry/2020/01/26/231500

以下にはABC152のE問題 Flatten のネタバレが含まれます。

この問題は多倍長整数を使用できる言語であれば愚直解が通ります。Haskellで書かれた愚直解のコードは、例えばSubmission #9632460 - AtCoder Beginner Contest 152が簡潔で読みやすいです。

foldr lcm 1 aの部分は、 $N$ 回「 $O\left(N\log A\right)$ ビットの整数と $O\left(\log A\right)$ ビットの整数の最大公約数（高々 $O\left(\log A\right)$ ビット）を求め、 $O\left(\log A\right)$ ビットの整数をそれで割り、その結果と $O\left(N\log A\right)$ ビットの整数を掛け合わせる」という計算を行うはずです。 $O\left(N\log A\right)$ ビットの整数と $\log A$ ビットの整数の最大公約数をユークリッドの互除法で求めると、多倍長除算は長除法（筆算）を用いるとして、時間計算量が $O\left(\left(N + \log A\right)\left(\log A\right)^2\right)$ となります。

残りの部分は、取るに足らない計算量です。

制約は $N=10^4, A=10^6$ なので、愚直解は雑な概算でΟの中が $4\times 10^9$ になります。時間制限は2秒であり、 $5\times 10^9$ サイクル以上のCPU時間があるので、これは余裕で間に合います。実際、多くのHaskellでの愚直解の提出は、200msから300msくらいで動作しています。

C++標準には残念ながら多倍長整数がありません。しかし、この問題に限っては位取り記数法を用いた多倍長整数を使う必要はありません。掛け算せず、因数*1の列として保持すればよいです。

それを利用した解法の提出が以下です。

Submission #9637654 - AtCoder Beginner Contest 152

全然間に合っていません。実際、この解法の時間計算量は $O\left(N^2 \left(\log A\right)^3\right)$ であり、愚直解より20倍ほど遅いことがわかります。つまり、3倍程度間に合いません。

手元で作った雑な最大ケースでは間に合ったため大丈夫だろうと思っていたのですが、よくよく考えると真の最大ケースは、「 $N$ 個の $A$ 未満の相異なる素数」です（テストケースの実行時間から推察すると、おそらくmax_02がこれです）。

そのケースを手元で動かした場合からの概算だと、ジャッジサーバーでは6秒くらいかかりそうだという感じだったので、いろいろな計算が大体合います。

そこで、自作の高速化したgcd関数を使えば間に合うのではないかと考えました。

以下は、最大公約数をもっと高速に求める（その4） - よーるで示した高速なgcd関数を、入力が $\frac{2^{64}}5$ を超えない場合に特化したものです。

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整数には $A^3$ が収まるので、因数を3つまとめて保持することにより、高速化を図ります。これをおしすすめると愚直解になるわけです。

ところで、このgcd関数は、g++でコンパイルすると、mov命令を減らしたいのかわかりませんが低速なcmova命令にコンパイルされてしまいます（最大公約数をもっと高速に求める（その2）【cmova命令は遅い】 - よーる）。clang++だとそのようなことはないため、clang++で提出します。

Submission #9639909 - AtCoder Beginner Contest 152

1825msというぎりぎりですが、通すことができました。

かかった時間から推察すると、自作のgcd関数は一回当たり300サイクル程度で動作しているということがわかりました。

*1:素因数ではありません