アカベコ20 [パソコン甲子園2019 予選 G]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0410

解説

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0410/judge/3897232/C++14

全探索で考えてみるが、日付を全探索するのは難しそう。
p1, p2, ..., pnの周期全体を見たときの周期はp1～pnの最小公倍数の周期になる。
これはちょっと計算量が怪しそう。

ここで発想の転換というか、経験則というかが必要になる。
制約を見ると、Nが20で弱点になっている。
メンバーの組み合わせは全部で2²⁰通りであり、10⁶くらいで悪くない。
メンバーの組み合わせが分かれば、その最小公倍数が出てくる周期になる。
その組み合わせが本当に出てくるかどうかを判定するには、その組み合わせに含まれないメンバーが登場しないかをチェックすればいい。
これは最小公倍数の約数であるかどうかを判定すればいい。
計算量的にはO(2^N*N)であり、ちょっと怪しい気もするが、祈りながら出すと通る。

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

    int ans = 0;
    rep(msk, 1, 1 << N) {
        ll lc = 1;
        rep(i, 0, N) if (msk & (1 << i)) lc = lcm(lc, P[i]);
        bool ok = true;
        rep(i, 0, N) if (!(msk & (1 << i))) if (lc % P[i] == 0) ok = false;
        if (ok) ans++;
    }
    cout << ans << endl;
}