题意：Face

数据范围

Strategy: 看到数据范围可以想到先把1e5以内的因子全部筛一遍, 不要问我为什么比赛的时候没想到,,, 然后pos[i]存i作为因子出现在那些数的下标, 然后每次询问从x的最大因子开始往下走, 询问pos[x_因子]有没有在区间[l, r]中出现过

服了不晓得为啥一定要用c++11, c++14会t

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
#define _rep(n, a, b) for (ll n = (a); n <= (b); ++n)
#define _rev(n, a, b) for (ll n = (a); n >= (b); --n)
#define _for(n, a, b) for (ll n = (a); n < (b); ++n)
#define _rof(n, a, b) for (ll n = (a); n > (b); --n)
#define oo 0x3f3f3f3f3f3fll
#define ll long long
#define db double
#define eps 1e-8
#define bin(x) cout << bitset<10>(x) << endl;
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
#define pdd pair<db, db>
#define pi acos(-1.0)
const ll maxn = 1e5 + 100;
const ll mod = 1e9;

vector<int> pos[maxn], sons[maxn];
int n, q;

void pre_work()
{
    _for(i, 1, maxn)
    {
        for (int j = 1; j * j <= i; ++j)
        {
            if (i % j == 0) {
                sons[i].emplace_back(j);
                if (i / j != j)sons[i].emplace_back(i / j);
            }
        }
        sort(all(sons[i]), greater<int>());
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    pre_work();
    cin >> n >> q;
    _rep(i, 1, n) {
        int v;
        cin >> v;
        for (auto& c : sons[v]) {
            pos[c].push_back(i);
        }
    }
    _rep(i, 1, q) {
        int l, r, x;
        cin >> l >> r >> x;
        for (auto s : sons[x]) {
            int lll = lower_bound(pos[s].begin(), pos[s].end(), l) - pos[s].begin();
            int rrr = upper_bound(pos[s].begin(), pos[s].end(), r) - pos[s].begin();

            if (rrr > lll) {
                cout << s << endl;
                break;
            }
        }
    }
}