mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #305 (Div. 1) C. Mike and Foam

問題読んだ時さっぱりわからなかったけど解説読んで目からウロコだった。

解法

各クエリに対して,数aに注目しているとすると,gcd(a,b)が1になるものの数は,
aの素因数がp1, p2, ..., pmと書けるとして,
(p1〜pmのうち0個の数を約数に持つ値の数) - (p1〜pmのうち1個の数を約数に持つ値の数) + (p1〜pmのうち2個の数を約数に持つ値の数) -...
という感じになります(要するに包除原理)。
異なる約数の数はこの制約だとたかだか6個しかないので1つのクエリは2^6 = 64の計算量で処理できます。

const int MAXN = 200020;
const int MAXM = 500050;
int divisor[MAXM];
int a[MAXN];
bool in[MAXN];
int cnt[MAXM];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i = 2; i < MAXM; i++) {
        if (divisor[i] == 0) {
            for (int j = 1; j * i < MAXM; j++) {
                divisor[i*j] = i;
            }
        }
    }
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll ans = 0;
    while (q--) {
        int x;
        cin >> x;
        x--;
        int X = a[x];
        vector<int> divs;
        while (X != 1) {
            if (find(divs.begin(), divs.end(), divisor[X]) == divs.end()) {
                divs.push_back(divisor[X]);
            }
            X /= divisor[X];
        }
        int m = divs.size();
        ll add = 0;
        for (int s = 0; s < (1<<m); s++) {
            int what = 1, size = 0;
            for (int i = 0; i < m; i++) {
                if ((s>>i)&1) {
                    size++;
                    what *= divs[i];
                }
            }
            if (in[x]) {
                cnt[what]--;
            }
            if (size&1) {
                add -= cnt[what];
            } else {
                add += cnt[what];
            }
            if (!in[x]) {
                cnt[what]++;
            }
        }
        if (in[x]) {
            ans -= add;
            in[x] = false;
        } else {
            ans += add;
            in[x] = true;
        }
        cout << ans << endl;
    }
    return 0;
}