题意：求$max\{(i,j)\}, smin<=i<=smax, wmin<=i<=wmax$，其中$smin<=smax<=10^9, wmin<=wmax<=10^9$，有$N<=1000$组数据

#include 
     
      using namespace std;int main() {	int cs, smin, smax, wmin, wmax, ans; scanf("%d", &cs);	while(cs--) {		scanf("%d%d%d%d", &smin, &smax, &wmin, &wmax);		if(smax>wmax) swap(smin, wmin), swap(smax, wmax);		ans=1;		if(wmin<=smax && smax<=wmax) ans=smax;		else {			--smin; --wmin;			for(int d=smax, pos; d; d=pos) {				pos=max(smax/(smax/d+1), wmax/(wmax/d+1));				if(smin>=d) pos=max(pos, smin/(smin/d+1));				if(wmin>=d) pos=max(pos, wmin/(wmin/d+1));				if(smax/d-smin/d>0 && wmax/d-wmin/d>0) { ans=d; break; }			}		}		printf("%d\n", ans);	}	return 0;}
     

　　

假设$smax<=wmax$

如果$wmin<=smax<=wmax$，显然答案就是$smax$

考虑枚举$d=gcd$，那么转换为在区间$[ \lfloor \frac{smin}{d} \rfloor, \lfloor \frac{smax}{d} \rfloor ] 和 [ \lfloor \frac{wmin}{d} \rfloor, \lfloor \frac{wmax}{d} \rfloor ]$找$[(i, j)]=1$表示存在$gcd(i,j)=d$

于是我就很sb了............我为什么一定要$[(i,j)]=1$呢.............然后膜拜了zyf千古神犇....发现其实$[(i,j)]>=1$就行了= =.............因为我很sb没想到.......倍数关系啊= =

于是分块查询即可..

复杂度$O(N4\sqrt{smax})$