Make One With GCD [yukicoder 917]

https://yukicoder.me/problems/no/917

前提知識

• 動的計画法

解説

https://yukicoder.me/submissions/393368

制約が少し特殊っぽい。
よくある方針として、全通りからgcdが1とならないものを引く方針で考える？
包除原理な感じもする。

いや、1つ使う要素を固定して、DPすればdpの添字はそれの約数に収まるな。
それで解けそう。
A1, A2, ...と順番にA[i]を使うときに最大公約数が1となる部分列の個数を求める。
このとき、A[i]を使うと決めたら、j<iを満たすA[j]は使う組み合わせは求まっているので、A[j]はすべて使わないことにする。
あとは、
dp[g] := gcdがgである部分列の総数
をmapで表現しながら、求めていく。

int N, A[50];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    ll ans = 0;
    rep(i, 0, N) {
        map<int,ll> dp;
        dp[A[i]] = 1;
        rep(j, i + 1, N) {
            map<int, ll> pd;
            fore(p, dp) {
                // 採用する
                pd[gcd(p.first, A[j])] += p.second;
                // 採用しない
                pd[p.first] += p.second;
            }
            swap(dp, pd);
        }
        ans += dp[1];
    }
    cout << ans << endl;
}