lessons/参考实现/03-Bitset/CodeForces-1097F.cpp

#include <bitset>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    constexpr int max_value = 7000;
    int n, q; cin >> n >> q;

    vector<int> mu(max_value + 1), primes;
    vector<bool> composite(max_value + 1);
    mu[1] = 1;
    for (int i = 2; i <= max_value; ++i) {
        if (!composite[i]) primes.push_back(i), mu[i] = -1;
        for (int p : primes) {
            if (i * p > max_value) break;
            composite[i * p] = true;
            if (i % p == 0) { mu[i * p] = 0; break; }
            mu[i * p] = -mu[i];
        }
    }

    vector<bitset<max_value + 1>> inverse_mask(max_value + 1);
    for (int v = 1; v <= max_value; ++v) {
        for (int k = 1; v * k <= max_value; ++k) {
            if (mu[k] != 0) inverse_mask[v].set(v * k);
        }
    }
    vector<bitset<max_value + 1>> state(n + 1);
    string output;
    while (q--) {
        int type, x; cin >> type >> x;
        if (type == 1) {
            int v; cin >> v; state[x].reset();
            for (int d = 1; d * d <= v; ++d) if (v % d == 0) {
                state[x].set(d); state[x].set(v / d);
            }
        } else if (type == 2) {
            int y, z; cin >> y >> z; state[x] = state[y] ^ state[z];
        } else if (type == 3) {
            int y, z; cin >> y >> z; state[x] = state[y] & state[z];
        } else {
            int v; cin >> v;
            output.push_back(char('0' + ((state[x] & inverse_mask[v]).count() & 1U)));
        }
    }
    cout << output << '\n';
}