题目概述

给你 $\{a_n\}$ ，给出 $m$ 个询问 $l,r,d$ 表示询问 $a_l\times a_{l+1}\times\cdots\times a_r$ 是不是 $d$ 的倍数。

解题报告

签到题送温暖，你只需要质因数分解一下，然后线段树动态开点查询就行了。

示例程序

#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
const int maxn=100000,maxa=100000,maxt=30000000;

int te,n,m,p[maxa+5];bool pri[maxa+5];
int len,ro[maxa+5],ls[maxt+5],rs[maxt+5],sum[maxt+5];

inline void Make(){
    pri[0]=pri[1]=true;
    for (int i=2;i<=maxa;i++){
        if (!pri[i]) p[++p[0]]=i;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=maxa;j++)
            if (i%p[j]) pri[t]=true; else {pri[t]=true;break;}
    }
}
#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<1)+(tot<<3)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
#define newnode (ls[++len]=0,rs[len]=0,sum[len]=0,len)
void Insert(int &p,int pos,int k,int l=1,int r=n){
    if (!p) p=newnode;sum[p]+=k;if (l==r) return;int mid=l+(r-l>>1);
    if (pos<=mid) Insert(ls[p],pos,k,l,mid); else Insert(rs[p],pos,k,mid+1,r);
}
int Ask(int p,int L,int R,int l=1,int r=n){
    if (!p||R<l||r<L) return 0;if (L<=l&&r<=R) return sum[p];int mid=l+(r-l>>1);
    return Ask(ls[p],L,R,l,mid)+Ask(rs[p],L,R,mid+1,r);
}
inline void Div(int x,int pos){
    for (int i=1,tot;i<=p[0]&&p[i]*p[i]<=x;i++)
        if (!(x%p[i])) {tot=0;while (!(x%p[i])) tot++,x/=p[i];Insert(ro[p[i]],pos,tot);}
    if (x>1) Insert(ro[x],pos,1);
}
inline bool check(int x,int L,int R){
    for (int i=1,tot;i<=p[0]&&p[i]*p[i]<=x;i++)
        if (!(x%p[i])) {tot=0;while (!(x%p[i])) tot++,x/=p[i];if (Ask(ro[p[i]],L,R)<tot) return false;}
    if (x>1&&Ask(ro[x],L,R)<1) return false;return true;
}
int main(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
    for (Make(),readi(te);te;te--){
        readi(n);readi(m);len=0;memset(ro,0,sizeof(ro));
        for (int i=1,x;i<=n;i++) readi(x),Div(x,i);
        for (int i=1,L,R,x;i<=m;i++) readi(L),readi(R),readi(x),puts(check(x,L,R)?"Yes":"No");
    }
    return 0;
}