Official

C - Multiple Sequences Editorial by kort0n


\(A_N = 1, 2, \ldots, M\) の場合について答えを求め、それらの総和を求めます。\(A_N\) を固定したときの答えは、各素因数が掛けられる回数が増加する場所に着目することにより、 ( \(A_N\) の素因数の種類数) 個の二項係数の積で表すことが出来ます。

\(1, 2, \ldots, M\) の素因数の種類数の総和は \(O\left(M\log M\right)\) と評価出来ます。以上より、二項係数の前計算の時間を除いて、この問題を \(O\left(M \log M\right)\) 時間で解くことが出来ました。