最大公约数（$gcd$）**【题目描述】** 给出$ n $个正整数$ai$， 标号$ 1，2，…，n$。 有$ m $个询问。 每个询问包含三个参数$ g$，$l$，$r$， 表示询问第$ l $个到第$ r $个数满足与$ g $的最大公约数大于$ 1$的所有数中， 最大的数是多少， 并统计有多少个最大的数。 **【输入格式】** 第一行两个正整数 $n，m$， 表示正整数的数量和询问的数量。 第二行$ n $个正整数， 表示$a_i$。 接下来$ m $行， 每行三个正整数$ g，l，r$。 **【输出格式】** 对于每个询问， 输出一行答案， 包括两个数， 分别是最大的数以及出现次数。 如果不存在， 则输出$-1$ $-1$。 **【输入样例】** $6$ $5$ $1$ $2$ $3$ $4$ $5$ $4$ $2$ $1$ $5$ $121$ $1$ $6$ $3$ $2$ $6$ $5$ $5$ $5$ $24$ $4$ $6$ **【输出样例】** $4$ $1$ $-1$ $-1$ $3$ $1$ $5$ $1$ $4$ $2$ **【 数据范围与约定】** 对于 $100\%$的数据， $1 ≤ n,m,g,ai ≤ 100000，1 ≤ l ≤ r ≤ n$ |数据编号 |$n$，$m$|其它| | ------------- |-------------| -----| | $0$~$1$ | $≤ 1000$ | | $2$~$4$|$ ≤ 10^5 $ |$l=r$ | | $5$~$6$ |$ ≤ 10^5 $ | 所有$a_i$，$g$ 都是偶数 | |7~9|$ ≤ 10^5 $ | **题解：** 对于每一个素数，将所有是这个素数的倍数的数加入线段树中，最多大约$10000$棵线段树，所以要动态开点，求出$max$后再建一棵线段树统计答案出现的次数。 $Code：$
#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<algorithm>#define N 100005using namespace std;int treemaxnum[N*200],treemaxlson[N*200],treemaxrson[N*200];int treenumnum[N*20],treenumlson[N*20],treenumrson[N*20];int prime[N],pri[N],pre[N],pred[N],n,m,a[N],p[N];int cntmax,cntnum,rootmax[N],rootnum[N];void buildmax(int &o,int l,int r,int x,int y){if(!o)o=++cntmax;if(l==r){treemaxnum[o]=max(treemaxnum[o],y);return;}int mid=(l+r)>>1;if(x<=mid)buildmax(treemaxlson[o],l,mid,x,y);else buildmax(treemaxrson[o],mid+1,r,x,y);treemaxnum[o]=max(treemaxnum[treemaxlson[o]],treemaxnum[treemaxrson[o]]);}int querymax(int o,int l,int r,int x,int y){if(!o)return -1;if(l==x&&r==y)return treemaxnum[o];int mid=(l+r)>>1;if(y<=mid)return querymax(treemaxlson[o],l,mid,x,y);elseif(x>mid)return querymax(treemaxrson[o],mid+1,r,x,y);elsereturn max(querymax(treemaxlson[o],l,mid,x,mid),querymax(treemaxrson[o],mid+1,r,mid+1,y));}void buildnum(int &o,int l,int r,int x){if(!o)o=++cntnum; if(l==r){treenumnum[o]++;return;}int mid=(l+r)>>1;if(x<=mid)buildnum(treenumlson[o],l,mid,x);else buildnum(treenumrson[o],mid+1,r,x);treenumnum[o]=treenumnum[treenumlson[o]]+treenumnum[treenumrson[o]];}int querynum(int o,int l,int r,int x,int y){if(!o)return 0;if(l==x&&r==y)return treenumnum[o];int mid=(l+r)>>1;if(y<=mid)return querynum(treenumlson[o],l,mid,x,y);elseif(x>mid)return querynum(treenumrson[o],mid+1,r,x,y);elsereturn querynum(treenumlson[o],l,mid,x,mid)+querynum(treenumrson[o],mid+1,r,mid+1,y);}int main(){freopen("gcd.in","r",stdin);freopen("gcd.out","w",stdout);memset(prime,true,sizeof(prime));prime[1]=false;int num=0;treemaxnum[0]=-1;for(int i=2;i<=N;i++){if(prime[i]){pri[++num]=i;pre[i]=1;pred[i]=num;}for(int j=1;j<=num&&i*pri[j]<=N;j++){prime[i*pri[j]]=false;pre[i*pri[j]]=i;if(i%pri[j]==0)break;}}scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){int k=a[i];num=0;while(k!=1){p[++num]=k/pre[k];k=pre[k];}sort(p+1,p+1+num);num=unique(p+1,p+num+1)-p-1;for(int j=1;j<=num;j++)buildmax(rootmax[pred[p[j]]],1,n,i,a[i]);}for(int i=1;i<=n;i++)buildnum(rootnum[a[i]],1,n,i);while(m--){int g,l,r;scanf("%d%d%d",&g,&l,&r);int k=g,mx=-1,sum=0;num=0;while(k!=1){p[++num]=k/pre[k];k=pre[k];}sort(p+1,p+1+num);num=unique(p+1,p+num+1)-p-1;for(int j=1;j<=num;j++)mx=max(mx,querymax(rootmax[pred[p[j]]],1,n,l,r));if(mx==-1)puts("-1 -1");else{sum=querynum(rootnum[mx],1,n,l,r);printf("%d %d\n",mx,sum);}}return 0;}
