区间 \(\left( l,r \right]\) 中存在 \(n\) 的倍数的充要条件是 \(\left\lfloor \frac{r}{n}\right\rfloor > \left\lfloor \frac{l}{n}\right\rfloor\)。
证明：记有整数 \(k\) 满足 \(k \times n \in \left( l,r \right]\)。
那么有
\[\displaystyle l < k \times n \leqslant r \Longleftrightarrow \dfrac{l}{n} < k \leqslant \dfrac{r}{n} \Longleftrightarrow \left\lfloor \frac{l}{n}\right\rfloor < \left\lfloor \frac{r}{n}\right\rfloor
\]
证毕。
记 \(\gcd(x,y)=k\)，我们可以枚举 \(k\)，因为 \(a \leqslant x \leqslant b\)，所以我们可以枚举 \(k\)。
但暴力枚举 \(k\) 肯定是会超时，那我们就用整除分块优化。
没学过整除分块可以看这个。
Code
#include <bits/stdc++.h>
using namespace std;
int n;
int a,b,c,d;
int last,ans;
int main() {
#ifdef ONLINE_JUDGE == 1
freopen("melina.in","r",stdin);
freopen("melina.out","w",stdout);
#endif
cin >> n;
for(int t = 1;t <= n; t++) {
cin >> a >> b >> c >> d;
for(int i = 1;i <= b && i <= d; i = last + 1) {
last = min(d / (d / i),b / (b / i));
// 整除分块的右端点，实际是范围内的最大值
if(b / last > (a - 1) / last && d / last > (c - 1) / last)
ans = last;// 利用性质
}
cout << ans << "\n";
}
#ifdef ONLINE_JUDGE == 1
fclose(stdin);
fclose(stdout);
#endif
return 0;
}