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

問題文

http://codeforces.com/contest/547/problem/C

解法

与えられた値を素因数分解して出てくる素数の数は高々6個しかない．
gcd を考えるときはこれだけで十分である．
今回は直接答えを求めず，gcd(a, b) != 1 となる個数を求めて最後にトータルから引くことにする．

値 a を素因数分解して出てきた素数を p1, p2, ..., pk とする．
また，今の棚にあるお酒で，値 v と互いに素でないものの個数を vs[v] と表すことにする．
すると，値 a が追加された時に gcd(a, b) != 1 となる個数の増減は，
vs[p1] + vs[p2] + ... + vs[pk] - vs[p1 * p2] - vs[p1 * p3] - ...
のように包除で求めることができる．
項の個数は 2^6 しかないので，この部分は愚直に計算して良い．
これを各クエリごとにやるので，クエリパートは O(2^6 * q) となる．
前計算 （p1 とか求める部分）も同様なのでこれで解ける．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    constexpr int max_val = 1 << 19;
    vector<bool> is_prime(max_val, true);
    vector<int> prime;
    for(int i = 2; i < max_val; ++i) {
        if(is_prime[i]) {
            prime.push_back(i);
            for(int j = i * 2; j < max_val; j += i) {
                is_prime[j] = false;
            }
        }
    }

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    vector<vector<int>> ps(n);
    auto insert_val = [&] (vector<int>& v, int val) {
        vector<int> added = {val};
        for(auto y : v) {
            added.push_back(-y * val);
        }
        v.insert(end(v), begin(added), end(added));
    };
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        int x = a[i];
        for(auto p : prime) {
            if(p * p > x) break;
            if(x % p == 0) {
                insert_val(ps[i], p);
                while(x % p == 0) x /= p;
            }
        }
        if(x > 1) insert_val(ps[i], x);
    }

    ll used_num = 0, tans = 0;
    vector<bool> used(n);
    vector<int> vs(max_val);
    while(q--) {
        int idx; cin >> idx;
        idx--;
        if(used[idx]) {
            used_num -= 1;
            for(auto x : ps[idx]) {
                const int sign = x < 0 ? 1 : -1;
                vs[abs(x)]--;
                tans += sign * vs[abs(x)];
            }
        } else {
            used_num += 1;
            for(auto x : ps[idx]) {
                const int sign = x < 0 ? -1 : 1;
                tans += sign * vs[abs(x)];
                vs[abs(x)]++;
            }
        }
        used[idx] = !used[idx];
        cout << used_num * (used_num - 1) / 2 - tans << endl;
    }
}

感想

これ苦手．ジャッジ解のコードは遠回りせず直接求めるもので，かなり簡潔だった．
多分僕がジャッジ解と同じように書くとバグるからこれで良かったのかも．