问题相当于找到一个最大的k满足在$[x_1,x_2]$，$[y_1,y_2]$中都有k的倍数

等价于$\frac{x_2}{k}>\frac{x_1-1}{k}$且$\frac{y_2}{k}>\frac{y_1-1}{k}$

注意到这只有$O(\sqrt{n})$种取值，于是可以分段计算，做到$O(\sqrt{n})$每次询问

 

#include
     
      int T,a,b,c,d,i,j,t;inline void up(int&a,int b){if(a>b)a=b;}int main(){  for(scanf("%d",&T);T--;printf("%d\n",t)){    scanf("%d%d%d%d",&a,&b,&c,&d),a--,c--;    if(b>d)t=a,a=c,c=t,t=b,b=d,d=t;    if(d/b>c/b)t=b;else for(i=1;i<=b;i=j+1){      j=b/(b/i),up(j,d/(d/i));      if(i<=a)up(j,a/(a/i));      if(i<=c)up(j,c/(c/i));      if(b/j>a/j&&d/j>c/j)t=j;    }  }  return 0;}