Codeforces #523 div2 C

問題

数列a1, a2, ..., anが与えられて、そこからいくつかの要素を、順序を変えずに取り出した数列b1, b2, ..., bkについて考える。k>1かつ、1 <= i <= kなる任意のbiがiで割り切れるようなものの個数を10e9+7で割った値を求めよ。
1 <= n <= 100,000
1 <= ai <= 1,000,000

Problem - C - Codeforces

解く

ぱっと思いつくのが
dp[n+1][n+1]
dp[i][0] = 1;
dp[i][j] = dp[i-1][j] (if ai % j != 0)
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] (if ai % j == 0)
みたいなdpで、最後にdp[n]を1番目からn番目まで足せばいいんですが、愚直に実装するともちろん時間が足りません。

そこでvector <map<int, int>> dp(n+1)を作って約数として出てくる部分だけ考えようとする。iごとにaiの約数を調べ、大きい方から順に更新していく。が、MLE。

ここでようやくDPを1次元に落とせることに気づき、map<int, int> dpでやろうとするが、今度は更新の順番を間違えていることに気づく。（降順に更新するのはわかっていたけど、約数のペアを同じタイミングで更新していた。ちゃんとvectorに放り込んでソートしましょう)

やっと通ると思って投げると、今度はTLE。
よく考えたら脳死でmapを使うとaiの約数のうちnより大きなものまで更新してしまっている。O(10⁵ * √10⁶)でギリ間に合わないんだろうかとか思いながら、ちゃんとvector dp(n+1)になおしてAC

めっちゃ時間かかってしまった。