SRM643 div.2 500 / div.1 250 TheKingsFactorization

研究室の練習会に途中参加してdiv2 easyしか解けなかった

問題

TopCoder Statistics - Problem Statement
N(10^18以下)と、Nを素因数分解したときの、全ての素因数を昇順に並べた列(a_1, a_2, ...)のうちprime = {a_i | iは奇数}となる列が与えられる。元の列を復元せよ(Nを素因数分解せよ)。

解法

解法自体はソースコードみた方が早い。
要は、i=2からi^3 <= Nとなるまで割れるだけ割るだけ。
なぜこれでいけるかを説明する。

1. 素因数の列の長さが偶数となる場合
   • 素因数の列(a_1, ..., a_(n-2), a_(n-1), a_n)を考えたとき、a_1, a_3, ..., a_(n_3), a_(n-1)は与えられているので、a_2, a_4, ..., a_(n-2)まで求めてしまえば、a_nはa_n以外の全てでNを割ることで求めることができる。よって、a_(n-2)が最大どこになるかを考えればよい。
   • a_(n-2)が一番大きくなるのは、a_(n-2)とa_(n-1)とa_nが全て一致するときである。よって、k^3 <= Nまで調べればよい。
2. 素因数の列の長さが奇数となる場合
   • 素因数の列(a_1, ..., a_(n-2), a_(n-1), a_n)を考えたとき、a_1, a_3, ..., a_(n_2), a_nは与えられているので、a_2, a_4, ..., a_(n-3)まで求めてしまえば、a_(n-1)はa_(n-1)以外の全てでNを割ることで求めることができる。よって、a_(n-3)が最大どこになるかを考えればよい。
   • a_(n-3)が一番大きくなるのは、a_(n-3)とa_(n-2)とa_(n-1)とa_nが全て一致するときである。よって、k^4 <= Nまで調べればよい。

以上より、k^3 <= Nまで調べればよいことがわかる。

計算量

コード

pythonでも間に合う(最大786ms)。