bzoj 5358[Lydsy1805月赛]口算训练

bzoj 5358[Lydsy1805月赛]口算训练

​​ begin.lydsy.com/JudgeOnline/upload/201805.pdf

维护主席树 主席树上维护 每种质因数分别出现了多少次 判断是否可行

直接暴力枚举这个数的质因数即可 最多6种情况判断我区间中这些质因数的个数是否多余我当前询问的数的这种数的质因数个数 常数很小

#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10;struct node{ int left,right,v; }tree[N*410];bool not_prime[N];int num,rt[N],n,m,prime[N],tot,T,id[N];inline void init(){ for (int i=2;i<=1e5;++i){ if(!not_prime[i]) prime[++tot]=i,id[i]=tot; for (int j=1;prime[j]*i<=1e5;++j){ not_prime[prime[j]*i]=1; if (i%prime[j]==0) break; } }}inline void insert1(int &x,int l,int r,int p,int v){ tree[++num]=tree[x];x=num;int mid=l+r>>1; if (l==r) {tree[x].v+=v;return;} if (p<=mid) insert1(tree[x].left,l,mid,p,v); else insert1(tree[x].right,mid+1,r,p,v);}inline bool query(int rt1,int rt2,int l,int r,int p,int v){ if (l==r){if (tree[rt2].v-tree[rt1].v>=v) return 1;else return 0;} int mid=l+r>>1; if (p<=mid) return query(tree[rt1].left,tree[rt2].left,l,mid,p,v); else return query(tree[rt1].right,tree[rt2].right,mid+1,r,p,v);}int main(){ //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); T=read();init();//printf("%d\n",tot); while(T--){ num=0;n=read();m=read(); for (int owo=1;owo<=n;++owo){ int x=read();rt[owo]=rt[owo-1]; for (int i=1;i<=tot&&x>=prime[i]*prime[i];++i){ if (x%prime[i]) continue;int t=0; while(x%prime[i]==0) ++t,x/=prime[i]; insert1(rt[owo],1,tot,i,t); }if (x!=1) insert1(rt[owo],1,tot,id[x],1); } for (int owo=1;owo<=m;++owo){ int l=read(),r=read(),d=read();bool flag=1; if (d==1) {puts("Yes");continue;} for (int i=1;i<=tot&&d>=prime[i]*prime[i];++i){ if (d%prime[i]) continue;int t=0; while(d%prime[i]==0) ++t,d/=prime[i]; flag&=query(rt[l-1],rt[r],1,tot,i,t); if (!flag) break; }if (d!=1) flag&=query(rt[l-1],rt[r],1,tot,id[d],1); flag?puts("Yes"):puts("No"); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。