yukicoder : No.3307 Almost Equal

なるほど。
https://yukicoder.me/problems/no/3307

問題

正整数A,B,C,Dが与えられる。
round(A*i/B)=round(C*i/D)
となる正整数iは何通りか。

解法

A/B＜C/Dとする。

• f(i) = A*i/B
• g(i) = C*i/D
• F(i) = round(f(i)) = floor( (A*i+B)/2B)
• G(i) = round(g(i)) = floor( (C*i+D)/2D)

とする。となるiの最大値をNとすると、解はとなるN以下の正整数iの個数である。
これは を求めればよく、sumの中身はfloor_sumで計算できる。

ll A,B,C,D;

__int128 F(__int128 v) {
	v*=A;
	__int128 ret=v/B;
	v%=B;
	if(v*2>=B) ret++;
	return ret;
	
}
__int128 G(__int128 v) {
	v*=C;
	__int128 ret=v/D;
	v%=D;
	if(v*2>=D) ret++;
	return ret;
	
}

template<class V> V floor_sum(V N,V M,V A,V B) {
	// sum(i=0...N-1) floor((A*i+B)/M)
	if(A<0) return floor_sum(N,M,-A,B+(N-1)*A); //Aが負の場合傾きを逆にする
	
	V ret=0;
	if(B>=M) ret+=N*(B/M), B%=M;
	if(A>=M) ret+=N*(N-1)/2*(A/M), A%=M;
	
	V Y=(A*N+B)/M;
	if(Y==0) return ret;
	//floor(Y/M)に達するX
	V X=Y*M-B;
	//Xの右側はY個ずつ
	ret+=(N-(X+A-1)/A)*Y;
	// 90度回転、Y=Nのラインは無視する
	ret+=floor_sum(Y,A,M,(A-X%A)%A);
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C>>D;
	if(A*D==B*C) {
		cout<<-1<<endl;
		return;
	}
	if(A*D>B*C) {
		swap(A,C);
		swap(B,D);
	}
	__int128 N=0;
	for(i=59;i>=0;i--) {
		__int128 p=C*(N+(1LL<<i))*B-D*(N+(1LL<<i))*A;
		__int128 q=B*D;
		if(p<=q) N+=1LL<<i;
	}
	ll ret=floor_sum<__int128>(N,2*D,2*C,D)-floor_sum<__int128>(N,2*B,2*A,B);
	cout<<(ll)N-ret-1<<endl;
	
	
	
	
}

まとめ

なんかyukicoderはAtCoder以上にfloor_sumを使う問題が出てるような気もする。