题目描述
已知 \(A\leq x\leq B,C\leq y\leq D\),求 \(\gcd(x,y)\) 的最大值。
数据范围:\(1\leq T\leq 1000,1\leq A\leq B\leq 10^9,1\leq C\leq D\leq 10^9\)。
分析
考虑枚举 \(x,y\) 的公因子 \(d\)。
首先可以发现一个性质:区间 \([l,r]\) 中有 \(d\) 的倍数的充要条件是 \(\lfloor\frac{l-1}{d}\rfloor<\lfloor\frac{r}{d}\rfloor\)。
枚举 \(d\in [1,\min(B,D)]\),然后判断是否满足 \(\lfloor\frac{A-1}{d}\rfloor<\lfloor\frac{B}{d}\rfloor\) 且 \(\lfloor\frac{C-1}{d}\rfloor<\lfloor\frac{D}{d}\rfloor\)。可以发现 \(\lfloor\frac{D}{d}\rfloor\) 这种形式的式子可以分块算,最多只有 \(\sqrt{D}\) 种取值,每一块中 \(d\) 的最大值为 \(\min\Big(\Big\lfloor\frac{B}{\lfloor\frac{B}{l}\rfloor}\Big \rfloor,\Big\lfloor\frac{D}{\lfloor\frac{D}{l}\rfloor}\Big \rfloor\Big)\),因此分块枚举即可。
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
long long A,B,C,D,ans;
scanf("%lld %lld %lld %lld",&A,&B,&C,&D);
for(long long l=1,r;l<=B&&l<=D;l=r+1)
{
r=min(B/(B/l),D/(D/l));
if( (A-1)/r<B/r and (C-1)/r<D/r)
ans=r;
}
cout<<ans<<endl;
}
}