rt，今天重新看到这题，发现自己之前的代码有一个逆天错误

#include <bits/stdc++.h>
template<class T> void read(T &x) {
    x = 0; T f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - 48; x *= f;
}
template<class T> void write(T x) {
    if (x > 9) write(x / 10); putchar(x % 10 + 48);
}
template<class T> void print(T x, char ed = '\n') {
    if (x < 0) putchar('-'), x = -x; write(x), putchar(ed);
}
using namespace std; const int N = 300005, V = 100005, L = 600, inf = 0x3f3f3f3f;
int n, q, a[N], ans[N], lim, maxn; vector<int> h[V];
struct Dat { int l, r, id; }; vector<Dat> g[V];
template<class T> struct Seg {
    T b[N << 2];
    int ls(int x) { return x << 1; } int rs(int x) { return x << 1 | 1; }
    void build(int x, int l, int r, int k) {
        if (l == r) return void(b[x] = a[l] % k); int m = l + r >> 1;
        build(ls(x), l, m, k); build(rs(x), m + 1, r, k);
        b[x] = min(b[ls(x)], b[rs(x)]);
    }
    T qry(int x, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return b[x]; int m = l + r >> 1, ret = V;
        if (ql <= m) ret = qry(ls(x), l, m, ql, qr);
        if (qr > m) ret = min(ret, qry(rs(x), m + 1, r, ql, qr)); return ret;
    }
}; Seg<int> tr;
template<class T> struct ST {
    T a[20][L], n; void init(int m) { n = m; memset(a, 0x3f, sizeof a); }
    T qry(int l, int r) {
        if (l > r) return inf; int k = __lg(r - l + 1);
        return min(a[k][l], a[k][r - (1 << k) + 1]);
    }
    void mdf(int x, int v) {
        a[0][x] = v;
        for (int i = 1, l, r; (1 << i) <= n; ++i) {
            l = max(1, x - (1 << i) + 1), r = min(n - (1 << i) + 1, x);
            for (int j = l; j <= r; ++j) a[i][j] = v;
        }
    }
};
template<class T> struct block {
    int bl[N], br[N], tot, bel[N], B; ST<T> st; T pre[N], suf[N], t[N];
    void init(int n) {
        B = sqrtl(n + 1); memset(t, 0x3f, sizeof t);
        for (int i = 1; i <= n; ++i) bel[i] = (i % B == 1 ? ++tot : tot);
        st.init(tot); memset(pre, 0x3f, sizeof pre); memset(suf, 0x3f, sizeof suf);
        for (int i = 1; i <= tot; ++i) bl[i] = br[i - 1] + 1, br[i] = min(n, i * B);
    }
    void mdf(int x, int v) {
        st.mdf(bel[x], v); t[x] = v;
        for (int i = x; i <= br[bel[x]]; ++i) pre[i] = v;
        for (int i = x; i >= bl[bel[x]]; --i) suf[i] = v;
    }
    int qry(int l, int r) {
        if (bel[l] == bel[r]) {
            if (l == bl[bel[l]]) return pre[r]; if (r == br[bel[l]]) return suf[l];
            int ret = inf;
            for (int i = l; i <= r; ++i) ret = min(ret, t[i]); return ret;
        }
        return min({suf[l], pre[r], st.qry(bel[l] + 1, bel[r] - 1)});
    }
}; block<int> blk;
void solve1(int k) {
    if (g[k].size()) tr.build(1, 1, n, k);
    for (auto [l, r, id] : g[k]) ans[id] = tr.qry(1, 1, n, l, r);
}
void solve2() {
    blk.init(n);
    for (int i = maxn; i >= 1; --i) {
        for (int j : h[i]) blk.mdf(j, i);
        for (int j = 1; j * j <= i; ++j)
            if (!(i % j)) {
                if (j >= lim)
                    for (auto [l, r, id] : g[i])
                        ans[id] = min(ans[id], blk.qry(l, r) - i);
                if (j * j != i && i / j >= lim)
                    for (auto [l, r, id] : g[i / j])
                        ans[id] = min(ans[id], blk.qry(l, r) - i);
            }
    }
}
signed main() {
    read(n); read(q);
    for (int i = 1; i <= n; ++i) read(a[i]), h[a[i]].emplace_back(i);
    maxn = *max_element(a + 1, a + n + 1); tr.build(1, 1, n, V);
    for (int i = 1, l, r, k; i <= q; ++i)
        read(l), read(r), read(k),
        g[k].emplace_back(Dat{l, r, i}), maxn = max(maxn, k);
    lim = sqrtl(maxn << 1) + 1;
    for (int i = lim; i <= maxn; ++i)
        for (auto [l, r, id] : g[i]) ans[id] = tr.qry(1, 1, n, l, r);
    for (int i = 1; i < lim; ++i) solve1(i); solve2();
    for (int i = 1; i <= q; ++i) print(ans[i]); return 0;
}

本题有 $\mathcal{O}(n\sqrt{n})$ 次询问，注意我的 block 中的 qry 函数，会导致 l，r 同块的时候 $\mathcal{O}(\sqrt{n})$ 回答一组询问，使得复杂度变成 $\mathcal{O}(n^2)$。

正确的处理方式是同块时暴力求解，这样至多 $n$ 次 $\mathcal{O}(\sqrt{n})$，是对的。

希望出题人能卡一下这个。