CF1097F Alex and a TV Show
发布时间:2020-12-14 05:13:11 所属栏目:大数据 来源:网络整理
导读:题目 CF1097F Alex and a TV Show 做法 奇偶性,考虑用 (bitset) 维护, (Set[i][j]) 为第 (i) 个集合中 (j) 作为因子出现的次数 预处理 (yz[i]) ( (i) 中的因子) (1) :直接 (Set[x]=yz[y]) (2) :相加取奇偶相当于异或 (3) :相乘取奇
题目CF1097F Alex and a TV Show 做法奇偶性,考虑用(bitset)维护,(Set[i][j])为第(i)个集合中(j)作为因子出现的次数 预处理(yz[i])((i)中的因子) (1):直接(Set[x]=yz[y]) (2):相加取奇偶相当于异或 (3):相乘取奇偶相当于且 (4):(F(n))为(n)作为因子出现的次数,(f(n))为(n)的出现次数 My complete code#include<cstdio> #include<cstring> #include<iostream> #include<string> #include<algorithm> #include<bitset> using namespace std; typedef int LL; inline LL Read(){ LL x(0),f(1);char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar(); return x*f; } LL n,q; bitset<7009> yz[7009],Mu[7009],Set[100009]; LL prime[7009],mu[7009]; bool visit[7009]; inline void First(LL N){ mu[1]=1; LL tot(0); for(LL i=2;i<=N;++i){ if(!visit[i]){ mu[i]=-1; prime[++tot]=i; } for(LL j=1;j<=tot&&i*prime[j]<=N;++j){ visit[prime[j]*i]=true; if((i%prime[j])==0) break; else mu[i*prime[j]]=-mu[i]; } } } int main(){ First(7000); for(LL i=1;i<=7000;++i) for(LL j=i;j<=7000;j+=i) yz[j][i]=1,Mu[i][j]=mu[j/i]!=0; n=Read(),q=Read(); while(q--){ LL op(Read()),x(Read()),y(Read()); if(op==1){ Set[x]=yz[y]; }else if(op==2){ LL z(Read()); Set[x]=Set[y]^Set[z]; }else if(op==3){ LL z(Read()); Set[x]=Set[y]&Set[z]; }else printf("%d",(Set[x]&Mu[y]).count()&1); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |