登录—专业IT笔试面试备考平台_牛客网、

把每个数的质因数分解出来，用莫队做，找区间众数即可

// Problem: Magic Number Group
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/21592/G
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e6+9;
int a[N];
int L[N],R[N],pos[N];
int ans[N],num[N],c[N];//答案,出现i次,出现为i的数量
int res,p;
vector<int> v[N];
struct Q{int l,r,id;bool friend operator < (const Q &a,const Q &b){return pos[a.l]^pos[b.l]?pos[a.l]<pos[b.l]:pos[a.l]&1?a.r<b.r:a.r>b.r;}
}que[N];
void work(int id,int x){for(int i=2;i<=x/i;i++){if(x%i==0){v[id].push_back(i);while(x%i==0){x/=i;}}}if(x>1){v[id].push_back(x);}
}
void add(int pos){for(auto & i : v[pos]){num[c[i]]--;c[i]++;num[c[i]]++;res=max(res,c[i]);//维护最大}
}
void del(int pos){for(auto & i : v[pos]){num[c[i]]--;if(res==c[i] && !num[c[i]]){//如果不存在就减少res--;}c[i]--;num[c[i]]++;}
}
void solve(){int n,q;cin>>n>>q;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){v[i].clear();work(i,a[i]);}for(int i=1;i<=q;i++){cin>>que[i].l>>que[i].r;que[i].id=i;}int t=sqrt(n);for(int i=1;i<=t;i++){L[i]=(i-1)*t+1;R[i]=i*t;}if(R[t]<n){t++;L[t]=R[t-1]+1;R[t]=n;}for(int i=1;i<=t;i++){for(int j=L[i];j<=R[i];j++){pos[j]=i;}}sort(que+1,que+1+q);int l=1,r=0;for(int i=1;i<=q;i++){while(que[i].l>l){del(l++);}while(que[i].l<l){add(--l);}while(que[i].r>r){add(++r);}while(que[i].r<r){del(r--);}ans[que[i].id]=res;}for(int i=1;i<=q;i++){cout<<ans[i]<<'\n';}while(l<=r){//清空del(l++);}res=0;//清空
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;//多组while(t--){solve();}return 0;
}