RT
今天我们模拟赛T1是这样一道题：

给定 $l$ 和 $r$，求 $\max_{l\le x,y\le r \;\mathrm{and}\;x\ne y}\limits \gcd(x,y)$（$t$ 组数据）
$1\le t \le 10^3,1\le l,r\le 2\times10^9$

我的做法：从 $k=-l$ 开始从大到小枚举答案，显然 $l\sim r$ 之间有两个 $k$ 倍数且差为 $k$ 时最优，那么如果 $l\sim r$ 之间只有一个 $k$ 的倍数
如图：

那么直接把 $k$ 调小直到 $(n+1)k\le r$。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
const ll INF=0x7f7f7f7f7f,inf=0x3f3f3f3f3f;
namespace Yorihime_Nao{
	template<class T> T MAX(T x,T y){
		return x>y?x:y;
	}
	template<class T> T MIN(T x,T y){
		return x<y?x:y;
	}
	template<class T,class ... Arg> T MAX(T x,T y,Arg ... arg){
		return MAX(x>y?x:y,arg...);
	}
	template<class T,class ... Arg> T MIN(T x,T y,Arg ... arg){
		return MIN(x<y?x:y,arg...);
	}
	template<class T> T lowbit(T x){
		return x&-x;
	}
	template<class T> void SWAP(T &x,T &y){
		T qwq=x;
		x=y;
		y=qwq;
		return;
	}
}
using namespace Yorihime_Nao;
ll T;
ll x,y;
int main(){
//	freopen("pinesoot.in","r",stdin);
//	freopen("pinesoot.out","w",stdout);
	cin>>T;
	while(T--){
		cin>>x>>y;
		if(x%(y-x)==0&&y%(y-x)==0){
			cout<<y-x<<endl;
			continue;
		}
		for(int i=y-x;i>=1;i--){
			ll d=x/i*i;
			if(d<x)d+=i;
			if(d+i<=y){
				cout<<i<<endl;
				break;
			}
			ll B=(d+i)/i,l=B*i-y;
			i-=(l%B?l/B+1:l/B);
			i++;
//			cout<<i<<endl;
		}
	}
	return 0;
}

求证明时间复杂度（（（
tip：正解整除分块q