区间 $\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;
}