Official

D - M<=ab Editorial by en_translator


Regarding the condition that \(X\) is represented by two integers \(a\) and \(b\) between \(1\) and \(N\), imposing \(a\leq b\) does not restrict the set of integers, and the answer is invariant too. Thus, we now impose this condition.

When the answer \(X\) is represented by two integers \(a\) and \(b\) \((a\leq b)\) between \(1\) and \(N\), what are the possible \(a\)? We do not have to consider \(a>\lceil \sqrt M\rceil\), because \(\lceil \sqrt M\rceil<a\leq b\) thus \(M\leq \lceil \sqrt M\rceil^2<ab\), so the product of such two integers can never be an answer.
Next, for a fixed \(a\), we consider the possible value for \(b\). Since \(M\leq ab\), it is necessary that \(b\geq \frac{M}{a}\). Here, if \(\frac{M}{a}>N\), there is no conforming \(b\) corresponding to that \(a\). Conversely, if \(\frac{M}{a}\leq N\), we have \(\left\lceil \frac{M}{a} \right\rceil\leq N\) since \(N\) is an integer, so at least \((a,b)\) when \(b=\left\lceil \frac{M}{a} \right\rceil\) is valid. Moreover, for a fixed \(a(>0)\), \(ab\) monotonically increases on \(b\), so \(b>\left\lceil \frac{M}{a} \right\rceil\) cannot be answer because then it would be \(M\leq a\cdot \left\lceil \frac{M}{a} \right\rceil<ab\).

Therefore, the candidates of \(X\) that can be an answer are the value \(ab\) for all \(1\leq a\leq \lceil X\rceil\) and \(b=\left\lceil \frac{M}{a} \right\rceil\). The complexity for each \(a\) is \(O(1)\), for a total of \(O(\sqrt{X})\) time; since \(X\leq 10^{12}\), this is fast enough.
Hence, the problem has been solved.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

#define INF (long long)2e+18

int main() {
	long long n,m,x,ans=INF;
	cin>>n>>m;
	for(long long i=1;i<=n;i++){
		x=(m+i-1)/i;
		if(x<=n)ans=min(ans,i*x);
		if(i>x)break;
	}
	if(ans==INF)cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
}

posted:
last update: