由最大公因数的性质:且，易得到结论：对于每一个询问，我们只需在到这个区间中找到一个，使得对任意的成立。

  • 算法1
    先考虑最朴素的做法：
    对于每一次询问，求出到这个区间中的每一个数与的最大公因数，并记录最大的那一个。
    时间复杂度(为最大值)，很显然，对于本题的数据规模这个复杂度是不够的。

观察这个题的特点，发现虽然和都比较大，但是和被限制在的范围内。这个条件很有可能成为解题的关键。
涉及到最大公因数的问题，如果朴素的算法不能解决，那么从因子的角度去考虑无疑是一个有益的尝试。那么问题的关键就聚焦于：
1.找到的一个因子，使得在到这个区间内可以找到一个,满足(即d也是的一个因子)
2.最大

朝这个方向思考于是有了算法2

  • 算法2
    对于每一个询问中的，找到的每一个因子，在的所有因子中从大到小判断在到的范围内是否存在，使得这个因子同时也是的因子。找到的第一个满足条件的因子即为该次询问的答案。
    先尝试在线处理
    在每一次询问中，先找到的所有因子是很有必要的。对于的一个因子，为了能更快的在到中寻找，使得满足。可以对数组进行预处理。由于的范围在以内，可见的因子范围在1到1e5之间。容易想到对于到中每一个数用一个set<int>来保存每一个满足的。记这样的set为。这样，对对的每一个因子,利用set中的lower_bound函数即能在的时间内判断是否存在这样的
    详细见代码：
    #include <bits/stdc++.h>
using namespace std;
const int MAX_N=1e5+20;
int n,q;
int a[MAX_N];
//S[i]用来储存所有使得a[p]%i==0的p
set<int> S[MAX_N];
void input(){
  scanf("%d%d",&n,&q);
  for(int i=1;i<=n;i++){
      scanf("%d",&a[i]);
      for(int j=1;j*j<=a[i];j++){
          if(a[i]%j==0)   S[j].insert(i),S[a[i]/j].insert(i);
      }
      if(a[i]!=0) S[a[i]].insert(i);
  }
}
void solve(){
  int l,r,x;
  //V用来储存x的因子
  vector<int> V;
  while(q--){
      int ans=1;
      V.clear();
      scanf("%d%d%d",&l,&r,&x);
      for(int i=1;i<=x;i++){
          if(x%i==0)  V.push_back(i),V.push_back(x/i);
      }
      V.push_back(x);
      sort(V.begin(),V.end());
      for(int i=V.size()-1;i>=0;i--){
          auto p=S[V[i]].lower_bound(l);
          //判断是否找到符合的元素所在的位置是否在l到r之间
          if(p!=S[V[i]].end()&&l<=*p&&*p<=r){ans=V[i];break;}
      }
      printf("%d\n",ans);
  }
}
int main(){
 // freopen("1.in","r",stdin);
 input();
 solve();
}
    这样的时间复杂度是(为最大值)，虽然比算法1更快了一些，但依然不够解决这个问题
    于是考虑离线的算法
    离线算法的优势在于已知所有的查询，这样就可以利用已知的查询之间的关系来优化算法。在上一个在线处理的算法中使用了二分来查找第一个大于等于的额含有因子的,如果将查询按的值排序，在每次查询前删去存储的小于的数据，那么此次查询中最小的那一个就是所查找的，并且对后面的查询不造成影响。每一个数因子最多个，一共个数，所以最多删除次,时间复杂度(为的最大值,为的最大值)
    详细见代码：
    #include <bits/stdc++.h>
using namespace std;
const int MAX_N=1e5+5;
int n,q;
//d[i]用来储存所有使得a[p]%i==0的p，且d[i]递增。
//如果用queue来储存会出现内存超限的情况
list<int> d[MAX_N];
struct Node{
  int l,r,x,id;
};
bool cmp(Node &A,Node &B){
  return A.l<=B.l;
}
Node p[MAX_N];
int ans[MAX_N];
void input(){
  scanf("%d%d",&n,&q);
  int x;
  for(int i=1;i<=n;i++){
      scanf("%d",&x);
      for(int j=1;j*j<=x;j++){
          if(j!=x&x%j==0)   {
              d[j].push_back(i);
              if(j!=x/j)  d[x/j].push_back(i);
          }
      }
      d[x].push_back(i);
  }
  for(int i=1;i<=q;i++){
      scanf("%d%d%d",&p[i].l,&p[i].r,&p[i].x);
      p[i].id=i;
  }
}
void solve(){
  sort(p+1,p+q+1,cmp);
  //V用来储存x的所有因子
  vector<int> V;
  for(int i=1;i<=q;i++){
      V.clear();
      for(int j=1;j*j<=p[i].x;j++){
          if(p[i].x!=j&&p[i].x%j==0) {
              V.push_back(j);
              if(p[i].x/j!=j) V.push_back(p[i].x/j);
          }
      }
      V.push_back(p[i].x);
      sort(V.begin(),V.end());
      int len=V.size();
      for(int j=len-1;j>=0;j--){
          while(!d[V[j]].empty()&&d[V[j]].front()<p[i].l)   d[V[j]].pop_front();
          if(!d[V[j]].empty()&&d[V[j]].front()<=p[i].r) {ans[p[i].id]=V[j];break;}
      }
  }
  for(int i=1;i<=q;i++)   printf("%d\n",ans[i]);
}
int main(){
  //freopen("1.in","r",stdin);
 input();
 solve();
}
    </int>