NC229623 - Mike and Foam

题意

有个啤酒，第杯啤酒含有毫升的泡沫, 然后给你个架子，初始架子为空，然后让你每次取出或者放入一个啤酒，然后每次操作后要你输出当前这个架子上，互质的啤酒对数

数据范围

思路

因为是求解互质，我们其实我们可以把拆解成这种集合，其中是一个的质因数，那么考虑现在插入一个集合，那么我们要计算这个数字对于当前的贡献，其实就是计算架子上面有多少个数字和互质，

假设现在架子上面有个啤酒，

我们可以根据容斥可知，架子上和互质的数量为

我可以每次进来或者出去一个数字的时候，动态维护这么一个数量，

值得注意的是的情况需要特殊处理

代码

/**
 *    author: andif
 *    created: 16.09.2023 23:09:25
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
const db eps = 1e-9;
const int N = 5e5 + 6;
vi primes, is_primes(N);

void init() {
    fill(all(is_primes), 1);
    is_primes[1] = 0;
    rep(i, 2, N) {
        if (is_primes[i]) primes.eb(i);
        for (int j = 0; j < sz(primes) && i * primes[j] < N; ++j) {
            is_primes[i * primes[j]] = 0;
            if (i % primes[j] == 0) break;
        }
    }
    // for (auto x: primes) {
    //     bool ok = true;
    //     for (int i = 2; i * i <= x; ++i) {
    //         if (x % i == 0) ok = false;
    //     }
    //     if (!ok) de(x);
    // }
    // de(sz(primes));
}

int main() {
    qc;
    init();
    int n, q; cin >> n >> q;
    vi a(n), vis(n);
    rep(i, 0, n) cin >> a[i];
    vector<vi> p(n);
    rep(i, 0, n) {
        int x = a[i];
        for (int j = 0; primes[j] * primes[j] <= x; ++j) {
            if (x % primes[j] == 0) p[i].eb(primes[j]);
            while(x % primes[j] == 0) x /= primes[j];
        }
        if (x > 1) p[i].eb(x);
    }
    ll ans = 0;
    int tot = 0;
    vi cnt(N);
    while(q--) {
        int x; cin >> x;
        x--;
        int y = a[x];
        if (y == 1) {
            if (vis[x]) {
                ans -= tot - 1;
            } else {
                ans += tot;
            }
        } else {
            if (vis[x]) {
                ll ret = tot;
                rep(i, 1, (1 << sz(p[x]))) {
                    int cur = 1;
                    rep(j, 0, sz(p[x])) {
                        if (i & (1 << j)) {
                            cur *= p[x][j];
                        }
                    }
                    int fg = __builtin_popcount(i) & 1 ? -1 : 1;
                    ret += fg * cnt[cur];
                    cnt[cur]--;
                }
                ans -= ret;
            } else {
                ll ret = tot;
                rep(i, 1, (1 << sz(p[x]))) {
                    int cur = 1;
                    rep(j, 0, sz(p[x])) {
                        if (i & (1 << j)) {
                            cur *= p[x][j];
                        }
                    }
                    int fg = __builtin_popcount(i) & 1 ? -1 : 1;
                    ret += fg * cnt[cur];
                    cnt[cur]++;
                }
                ans += ret;
            }
        }
        tot += (vis[x] ? -1 : 1);
        // de(tot);
        vis[x] ^= 1;
        cout << ans << '\n';
    }
    return 0;
}