O - 你的名字。
哎，卡常。
考虑根号分治。当 \(k\le T\) 时我们对每种可能的 \(k\) 预处理 \(a_i\bmod k\)，然后分成 \(\sqrt{n}\) 块，每块块内维护前后缀最小值，对所有块再跑 ST 表。当询问两端点在同一块内时暴力查询，不在同一块内时分成整块和散块 \(\mathcal{O}(1)\) 查询，复杂度 \(\mathcal{O}(T(n+\sqrt{n}\log\sqrt{n})+\sum[k_i\le T])\)；当 \(k>T\) 时发现 \(\dfrac{V}{k}\) 不会太大，可以枚举 \(i\)，每次只考虑 \(a_j\in[ik,(i+1)k)\) 的位置，然后类似上述做法处理。
发现此时空间复杂度是 \(\mathcal{O}(\dfrac{mV}{T})\) 级别的，不太能行。不妨转为枚举 \(ik\)，此时不需要额外开空间。同时由于本题求最小值，我们只用保证 \(a_j\ge ik\) 即可，于是可以从大到小枚举，每次逐渐加入，单次修改复杂度为 \(\mathcal{O}(\sqrt{n}+(1+2+4+\ldots \sqrt{n}))=\mathcal{O}(\sqrt{n})\) 级别，总复杂度 \(\mathcal{O}(n\sqrt{n}+V\ln V+\sum[k_i>T])\)。
注意本题非常卡常，有几个细节需要注意：
-
适当调整块长，经试验取在 630 左右最优；
-
快读，以及其他所有常用、基本的卡常技巧，以及不要用 vector；
-
玄学的估价函数：可以大概预估一下两种方法需要的大概时间，然后考虑选哪种；
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
char gc() {
#if DEBUG
return getchar();
#endif
if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
return p1 == p2 ? ' ' : *p1++;
}
bool blank(char ch) {
return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
template <class T>
void read(T &x) {
double tmp = 1;
bool sign = 0;
x = 0;
char ch = gc();
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
if (ch == '.')
for (ch = gc(); isdigit(ch); ch = gc())
tmp /= 10.0, x += tmp * (ch - '0');
if (sign) x = -x;
}
void read(char *s) {
char ch = gc();
for (; blank(ch); ch = gc())
;
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
}
void read(char &c) {
for (c = gc(); blank(c); c = gc())
;
}
void push(const char &c) {
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <class T>
void write(T x) {
static T sta[35];
T top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) push(sta[--top] + '0');
}
template <class T>
void write(T x, char lastChar) {
write(x), push(lastChar);
}
} io;
struct Que{
int l,r,k,id;
}q[300005];
inline int cmpq(Que x,Que y){
return x.k<y.k;
}
int n,m,V,T,a[300005],b[300005],c[300005],ans[300005],lv[100005],rv[100005],lp[100005],rp[100005];
int siz,num,bel[300005],L[635],R[635],pr[635][635],sf[635][635],Log[635],f[12][635];
inline int qry(int l,int r){
int il=bel[l],ir=bel[r],o=Log[(ir-1)-(il+1)+1];
if(ir-il==1)return min(sf[il][l-L[il]+1],pr[ir][r-L[ir]+1]);
return min({sf[il][l-L[il]+1],pr[ir][r-L[ir]+1],f[o][(il+1)],f[o][(ir-1)-(1<<o)+1]});
}
inline void solve(int k){
for(int i=1;i<=n;++i)c[i]=a[i]%k;
for(int i=1;i<=num;++i){
pr[i][1]=c[L[i]];
for(int j=L[i]+1;j<=R[i];++j)pr[i][j-L[i]+1]=min(pr[i][j-L[i]],c[j]);
sf[i][R[i]-L[i]+1]=c[R[i]];
for(int j=R[i]-1;j>=L[i];--j)sf[i][j-L[i]+1]=min(sf[i][j-L[i]+2],c[j]);
}
for(int i=1;i<=num;++i)f[0][i]=pr[i][R[i]-L[i]+1];
for(int j=1;j<=Log[num];++j){
for(int i=1;i+(1<<j)-1<=num;i++){
f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]);
}
}
for(int x=lv[k];x<=rv[k];++x)if(q[x].r-q[x].l+1>siz)ans[q[x].id]=qry(q[x].l,q[x].r);
}
inline int cmpa(int x,int y){
return a[x]>a[y];
}
signed main(){
io.read(n),io.read(m),siz=630,num=(n+siz-1)/siz;
for(int i=1;i<=n;++i)bel[i]=(i-1)/siz+1;
for(int i=1;i<=num;++i)L[i]=(i-1)*siz+1,R[i]=i*siz;
R[num]=n;
Log[1]=0;for(int i=2;i<=num+2;++i)Log[i]=Log[i>>1]+1;
for(int i=1;i<=n;++i)io.read(a[i]),V=max(V,a[i]),b[i]=i;
for(int i=1;i<=m;++i)io.read(q[i].l),io.read(q[i].r),io.read(q[i].k),q[i].id=i,ans[i]=inf;
sort(q+1,q+m+1,cmpq);sort(b+1,b+n+1,cmpa);
for(int i=1;i<=n;++i)lp[a[b[i]]]=(lp[a[b[i]]]?lp[a[b[i]]]:i),rp[a[b[i]]]=i;
for(int i=1;i<=m;++i){
int l=q[i].l,r=q[i].r,k=q[i].k,id=q[i].id;T=max(T,k);
if(r-l+1<=siz){
for(int j=l;j<=r;++j)ans[id]=min(ans[id],a[j]%k);
continue;
}
lv[k]=(lv[k]?lv[k]:i),rv[k]=i;
}
int w=3*n+siz*Log[siz]-n*siz/m;
for(int i=1;i<=T;++i)if(w<2.7*(V/i-1)*(rv[i]-lv[i]+1))solve(i),lv[i]=0;
for(int i=1;i<=num;++i)for(int j=1;j<=R[i]-L[i]+1;++j)pr[i][j]=sf[i][j]=inf;
for(int j=0;j<=Log[num];++j)for(int i=1;i+(1<<j)-1<=num;++i)f[j][i]=inf;
for(int i=V;i>=1;i--){
for(int x=lp[i];x<=rp[i];++x){
int p=b[x],id=bel[p];
for(int i=p;i<=R[id];++i)pr[id][i-L[id]+1]=a[p];
for(int i=L[id];i<=p;++i)sf[id][i-L[id]+1]=a[p];
for(int j=0;j<=Log[num];++j){
int lt=max(1,id-(1<<j)+1),rt=min(id,num-(1<<j)+1);
for(int i=lt;i<=rt;++i)f[j][i]=a[p];
}
}
for(int j=1;j*j<=i;++j){
if(i%j)continue;
if(lv[j]){
for(int x=lv[j];x<=rv[j];++x){
int l=q[x].l,r=q[x].r,id=q[x].id;
if(r-l+1>siz)ans[id]=min(ans[id],qry(l,r)-i);
}
}
if(lv[i/j]&&i/j!=j){
for(int x=lv[i/j];x<=rv[i/j];++x){
int l=q[x].l,r=q[x].r,id=q[x].id;
if(r-l+1>siz)ans[id]=min(ans[id],qry(l,r)-i);
}
}
}
}
for(int i=1;i<=m;++i){
int l=q[i].l,r=q[i].r,id=q[i].id;
if(r-l+1>siz&&lv[q[i].k])ans[id]=min(ans[id],qry(l,r));
}
for(int i=1;i<=m;++i)io.write(ans[i],'\n');
return 0;
}