yukicoder : No.2882 Comeback

綺麗に解こうとすると苦労しそう。
https://yukicoder.me/problems/no/2882

問題

正整数A＜Bが与えられる。
A%m≧B%mとなるmは何通りか。

解法

A%mとA%(m-1)の差は、floor(A/m)=floor(A/(m-1))ならA/mである。
よって、floor(A/m)が一致する一連のmの間では、A%mは等差数列になる。

よってfloor(A/m)及びfloor(B/m)が一致する間では、A%mやB%mはいずれも等差数列なので、A%m≧B%mとなる区間は容易に計算できる。
あらかじめfloor(A/m)やfloor(B/m)が変わるタイミングを列挙しておき、各区間で上記計算を行おう。

int T;
ll A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>A>>B;
		vector<ll> C;
		for(i=1;i*i<=A;i++) C.push_back(i),C.push_back(A/i);
		for(i=1;i*i<=B;i++) C.push_back(i),C.push_back(B/i);
		sort(ALL(C));
		C.erase(unique(ALL(C)),C.end());
		reverse(ALL(C));
		C.push_back(0);
		
		ll ret=0;
		FOR(i,C.size()-1) {
			ll AF=A%C[i],BF=B%C[i];
			ll AD=A/C[i],BD=B/C[i];
			int sz=C[i]-C[i+1];
			
			
			if(AD==BD) {
				if(AF>=BF) ret+=sz;
			}
			else if(AF>=BF) {
				ret+=min((ll)sz,(AF-BF)/(BD-AD)+1);
			}
		}
		cout<<ret<<endl;
	}
}

まとめ

一から自分で解いたらもっと泥臭い実装しそう。