牛客练习赛58 E 最大GCD

首先很容易观察到那个 (s,t) 是假的，因为令 (s=t) 不会更劣
然后暴力找所有因子，分别扔进一个向量里，每次询问枚举答案到向量里二分找即可
复杂度证明考虑利用因子数量的宽界估计

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n,q,a[N];
vector<int> v[N];

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) {
        for(int j=1;j*j<=a[i];j++) {
            if(a[i]%j) continue;
            v[j].push_back(i);
            v[a[i]/j].push_back(i);
        }
    }
    while(q--) {
        vector<int> s,r;
        int l,R,x;
        cin>>l>>R>>x;
        for(int j=1;j*j<=x;j++) if(x%j==0) {
            s.push_back(j);
            r.push_back(x/j);
        }
        for(int j=r.size()-1;j>=0;j--) s.push_back(r[j]);
        reverse(s.begin(),s.end());
        int flag=1;
        for(int j=0;j<s.size();j++) {
            if(s[j]>1)
            if(upper_bound(v[s[j]].begin(),v[s[j]].end(),R)
               -upper_bound(v[s[j]].begin(),v[s[j]].end(),l-1)>0) {
                flag=s[j];
                break;
               }
        }
        cout<<flag<<endl;
    }
}