AtCoder Beginner Contest 341, D : Only one of two

問題文

　https://atcoder.jp/contests/abc341/tasks/abc341_d

問題概要

　正整数 $n, m, k$ ($n \neq m $) が与えられる．正整数であって，$n, m $ のどちらか一方でのみ割り切れる数の内，小さい方から $k$ 番目のものを求めよ．

制約

• $1 \leq n, m \leq 10^8$
• $1 \leq k \leq 10^{ 10 }$
• $n \neq m $

解法

　制約がそこそこ大きいので，正整数を順に試していって条件を満たすものを数えるというようなことはできません．なので，何か工夫をする必要があります．
　やや唐突ですが，「ある数 $x$ 以下の正整数の内，条件を満たすものの個数を求める関数」を $f$ とすると，$f( x ) \geq k$ となる最小の $x$ が求めたかった値ということになります．$f$ には単調性があるので，二分法をすることでより高速に答えを求められます．
　次は $f$ を実装する方法についてですが，その前に超重要なこととして，$a$ 以下の正整数の内 $y$ の倍数であるものの個数は $\left\lfloor \frac a b \right\rfloor$ です．よって，
\begin{equation*}
\left\lfloor \frac x n \right\rfloor + \left\lfloor \frac x m \right\rfloor
\end{equation*}
が「$x$ 以下の整数の内，$n, m $ の少なくとも一方で割り切れるものの個数」となります．このままだと余計なものまで数えているわけですが，何を数えてしまっているかというと，$n$ と $m $ の公倍数を 2 回ずつ余計に数えています．これを引けばよいので，先程の値から
\begin{equation*}
2 \left\lfloor \frac x { \mathrm{ lcm }( n, m ) } \right\rfloor
\end{equation*}
を引くことで $f( x )$ の値を求められます．
　以上により，問題を解くことができます．

コード

constexpr auto INF = LIM< LL >::max() / 2;

LL count( const LL N, const LL M, const LL T )
{
	return T / N + T / M - T / lcm( N, M ) * 2;

}

int main()
{
	IN( LL, N, M, K );

	LL lb = 0, ub = INF;
	while ( lb + 1 < ub )
	{
		const LL mid = ( lb + ub ) / 2;
		( count( N, M, mid ) < K ? lb : ub ) = mid;
	}

	cout << ub << endl;

	return 0;
}