Codeforces #256 Div2 D. Multiplication Table

こちらも割とすんなり。
http://codeforces.com/contest/448/problem/D

問題

整数N,M,Kが与えられる。
整数1～Nと1～Mをそれぞれ掛け合わせてできるN*M個の整数を昇順に並べたとき、K番目の値はいくつか。

解法

K番目の値Vを決め打ちし、V以下の数がK個以下かどうかを二分探索で判定する。
V以下の数のカウントはO(N)で出来るので、全体でO(N*log(NM))で済む。

ll N,M,K;

ll num(ll V) {
	ll ret=0;
	if(V<=0) return 0;
	for(ll x=1;x<=N;x++) ret+=min(V/x,M);
	return ret;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>K;
	ll L=0,R=1LL<<50;
	
	FOR(i,100) {
		ll M=(L+R)/2;
		if(num(M)>=K) R=M;
		else L=M+1;
	}
	
	cout << L <<endl;
}

まとめ

二分探索が思いつけばあっさり。