F - Alex and a TV Show

容斥+bitset
绝世好题




#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl; 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 1e5+10;
const int maxk = 7001;

bitset<maxk> G[maxn];// G[i] 表示第i个集合
bitset<maxk> b[maxk],c[maxk];// b[i][j] 为真代表i有j这个约数，c[i][j] 为真表示j是i的倍数并且 j/i 不是平方项的倍数
int n,q;
bool bad[maxk];
int main(void)
{
  ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); 
  cin>>n>>q;
  for(int i = 2;i < maxk; ++i){
    for(int j = i*i;j < maxk; j += i*i)
         bad[j] = 1;
  }
  for(int i = 1;i < maxk; ++i){
    for(int j = 1;j < maxk; ++j)
      b[i][j] =  (i%j == 0);
    for(int j = 1;i*j < maxk; ++j)
      if(!bad[j])
        c[i][j*i] = 1;
  }
  std::vector<bool> vec;
  int x,y,z,v,op;

  for(int i = 0;i < q; ++i){
    cin>>op;
    if(op == 1){
      cin>>x>>v;
      G[x] = b[v];
    }
    else if(op == 2){
      cin>>x>>y>>z;
      G[x] = G[y]^G[z];
    }
    else if(op == 3){
      cin>>x>>y>>z;
      G[x] = G[y]&G[z];
    }
    else{
      cin>>x>>v;
      cout<<(G[x]&c[v]).count()%2;
    }
  }
    

   return 0;
}