Educational Codeforces #20 F: Coprime Subsequences

事前に1~max(a[1],a[2],...,a[n])の約数を求めておく。
次に、約数qをもつ数を数えて
cnt[q]
のように表す。
部分列のgcdをgとしたときq|gを満たす空でない部分列を数えよう。
これは簡単で、qを約数にもつ数すべてについて、部分列に含むかどうかを考えて
cnt[q]^2-1
となる。
GCDがgであるような部分列の数をdp[g]とする。
dp[1]が解である。
dp[g]
= (gを約数に持つ部分列の数) - (gを約数に持つが最大公約数がgより大きいg'である部分列の数)
= cnt[g]^2-1 - Σ[g'はgの倍数](dp[g'])
この式の前半部分は先に説明した。
後半部分の計算を考えよう。
g'はgの倍数である。
⇔gはg'の約数
なのであるdp[g']が求まったとき、g'のg'以外の約数gについて、dp[g]からdp[g']を引く。g'>gが成り立つので
dpを値の大きい順に計算していけばいい。

計算量について
約数を計算する前処理は
θ(Σ√a[i])
dpは遷移は
約数の個数の最大値をmとしたとき
O(m*max(a))
10^5以下で最も約数が多いのは
83160であり約数の個数はたかだか128個なので間に合う。

広告を非表示にする