题目大意

给你一个序列$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;
}