Codeforces #412 Div1 A. Success Rate

残念ながら割と苦戦したたためレート減。
http://codeforces.com/contest/806/problem/A

問題

今Y名が問題を解いたところ、X名が正解した。
さらに何人かが問題を解いた結果、正解率がP/Q(約分済み)となるようにしたい。
最小何人問題を解く人を追加すればよいか。

解法

仮にa二人追加したとすると、正解率は[X/Y,(X+a)/(Y+a)]の範囲となる。
aが大きくなるほど、この範囲は増える。

よって二分探索などで[X/Y,(X+a)/(Y+a)]がP/Qを含むような最小のaを求めよう。
(Y+a)がQの倍数となることに注意すること。
aそのものを二分探索すると分数の大小比較の過程で64bitに収まらなくなるので、(Y+a)がQの何倍かについて二分探索するとよい。

int T;
ll X,Y,P,Q;

int ok(ll X,ll Y,ll P,ll Q,ll v) {
	P*=v;
	Q*=v;
	if(Q<Y) return 0;
	
	ll dif=Q-Y;
	if(P<X || P>X+dif) return 0;
	return 1;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>X>>Y>>P>>Q;
		if((X && P==0) || (X<Y && P==Q)) {
			cout<<-1<<endl;
			continue;
		}
		
		ll ret=(1LL<<60)/Q+1;
		for(i=59;i>=0;i--) if(ok(X,Y,P,Q,ret-(1LL<<i))) ret-=1LL<<i;
		cout<<Q*ret-Y<<endl;
	}
}

まとめ

本番64bitに収まらない方式を取ってしまい、急きょPythonで書いた。