ARC 114

Table of Contents

A - Not coprime

https://atcoder.jp/contests/arc114/tasks/arc114_a

50 以下の素数は15個である。

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

これらの積は $10^{18}$ 以下なので答えは long long int で収まる。 \begin{align*} \prod_{p \in \text{50 以下の素数}} p = 614,889,782,588,491,410 < 10^{18} \end{align*}

考えうる $Y$ の値はせいぜい $2^{15} - 1 = 32767$ 個なので全ての組み合わせを試して条件にあうもののうちの最小を求めれば良い。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll X(N);
    rep(i, N) cin >> X[i];

    vint used(55);
    for (ll x : X) {
        ll t = x;
        rep2(i, 2, t + 1) {
            if (x % i == 0) {
                used[i] = 1;
                while (x % i == 0) x /= i;
            }
        }
    }

    vll primes;
    rep(i, 50) {
        if (used[i]) primes.push_back(i);
    }

    ll ans = INF;
    int sz = primes.size();
    rep(state, 1ll << sz) {
        ll t = 1;
        rep(i, sz) {
            if ((state >> i) & 1) t *= primes[i];
        }
        int ok = 1;
        for (ll x : X) {
            if (gcd(t, x) == 1) {
                ok = 0;
                break;
            }
        }
        if (ok) chmin(ans, t);
    }
    cout << ans << endl;
}

B - Special Subsets

条件より $i$ から $f(i)$ に辺を張ったグラフを作り、このうちサイクルを成しているサブグラフの頂点集合が $T$ になる。 各サブグラフは独立しているからサイクルを成しているサブグラフの個数を $n$ とすると $2^n - 1$ が答え。

void solve() {
    ll N;
    cin >> N;
    vll f(N);
    rep(i, N) {
        cin >> f[i];
        f[i]--;
    }

    scc_graph graph(N);
    rep(i, N) {
        graph.add_edge(i, f[i]);
    }

    vvint scc = graph.scc();
    ll cnt = 0;
    for (auto& x : scc) {
        if (x.size() > 1) {
            cnt++;
        } else {
            // 大きさ1のときは自己ループしていればカウント
            if (x[0] == f[x[0]])
                cnt++;
        }
    }

    mint ans = ((mint)2).pow(cnt) - 1;
    cout << ans.val() << endl;
}