Translation #
Given a sequence of length and queries in format , find .
Solution #
Since is rather small, we can precalculate all the factors of all the numbers smaller than . Then, for each factor, we store all the such that contains this factor in ascending order.
For each query, we iterate all the factors from biggest to smallest and see if we can find some number in that contains this factor. We could use binary search to achieve this.
Code #
#include <bits/stdc++.h>
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define pb push_back
using namespace std;
const int N=1e5+5;
vector<int> p[N],fac[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,q;
cin>>n>>q;
for1(i,1e5){
for(int j=i;j<=1e5;j+=i) fac[j].pb(i);
}
for1(i,n){
int x;
cin>>x;
for(auto f:fac[x]) p[f].pb(i);
}
while(q--){
int l,r,x;
cin>>l>>r>>x;
for(int i=fac[x].size()-1;i>=0;i--){
int f=fac[x][i];
if(p[f].empty()) continue;
auto it=lower_bound(p[f].begin(),p[f].end(),l);
if(it!=p[f].end()&&*it<=r){
cout<<f<<endl;
break;
}
}
}
return 0;
}