BZOJ 5358 [Lydsy1805月赛]口算训练

题目大意

给你一个序列$a$，每次询问$a_l * a_{l+1} * ... * a_r$是不是$d$的倍数。

分解每个数为质因数，塞到主席树里就可以了……

注意可以$O(\sqrt{n})$分解，也可以直接在线筛的时候就筛出来最小的质因数$prime[j]$.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,T;
int prm[100010],frm[100010],cnt,p[100010],q[100010],tot,sum[44000000],ls[44000000],rs[44000000],rt[100010],pts;
bool use[100010],existans;
void initiate()
{
	int i,j;
	for(i=2;i<=100000;++i)
	{
		if(!use[i]) prm[++cnt]=i,frm[i]=i;
		for(j=1;j<=cnt&&i*prm[j]<=100000;++j)
		{
			use[i*prm[j]]=true;
			frm[i*prm[j]]=prm[j];
			if(i%prm[j]==0) break;
		}
	}
}
void insert(int lp,int &rp,int l,int r,int x,int y)
{
	rp=++pts;
	sum[rp]=sum[lp]+y,ls[rp]=rs[rp]=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(x<=mid) insert(ls[lp],ls[rp],l,mid,x,y),rs[rp]=rs[lp];
	else insert(rs[lp],rs[rp],mid+1,r,x,y),ls[rp]=ls[lp];
}
int query(int lp,int rp,int l,int r,int x)
{
	if(l==r) return sum[rp]-sum[lp];
	int mid=(l+r)>>1;
	if(x<=mid) return query(ls[lp],ls[rp],l,mid,x);
	else return query(rs[lp],rs[rp],mid+1,r,x);
}
void split(int x)
{
	int i;
	tot=0;
	while(x!=1)
	{
		++tot,p[tot]=frm[x],q[tot]=0;
		while(x%p[tot]==0) x/=p[tot],q[tot]++;
	}
}
void calculate()
{
	memset(rt,0,sizeof rt),pts=0;
	int i,j,t,l,r,d;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
	{
		scanf("%d",&t);
		split(t);
		for(j=1;j<=tot;++j) insert(rt[i],rt[i],1,100000,p[j],q[j]);
		rt[i+1]=rt[i];
	}
	while(m--)
	{
		existans=false;
		scanf("%d%d%d",&l,&r,&d);
		split(d);
		for(i=1;i<=tot;++i) if(query(rt[l-1],rt[r],1,100000,p[i])<q[i]) {puts("No"),existans=true;break;}
		if(!existans) puts("Yes");
	}
}
int main()
{
	initiate();
	scanf("%d",&T);
	while(T--) calculate();
	return 0;
}