AtCoder が提供しているABC（AtCoder Beginner Contest）296 のD問題をC++とPythonで解いてみました。ABC296は、2023年4月1日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 M<=ab（Difficulty : 999）
問題はリンク先をご覧ください。
掛け算についての問題ですが、探索範囲に工夫が必要です。AtCoder Problems による Difficulty は 999 でした。
解答案
$a \leqq b \; (\leqq N)$ と考えても答えは変わりません。これは、問題の条件を満たす $a$ と $b$ に対して、大きくない方を $a$ として、残りを $b$ と置き換えればよいからです。
$a$ に対して、$b = M / a$ または $b = M / a + 1$ とします。$1 \leqq a \leqq \sqrt{M}$ の範囲で、$a \times b$ の $M$ 以上の最小値を調べれば十分な範囲の探索となります。
$M$ の上限は $10^{12}$ ですが、$\sqrt{M} = 10^6$ まで調べればよいため、計算量的には間に合います。
C++ プログラム例（ABC296D）
変数 $r = \sqrt{M}$ として、$1 \leqq a \leqq r + 1$ に対して、上記の方針で調べます。変数 result の初期値を十分大きくしておいて、そのままの値であれば、$-1$ を出力します。 $r + 1$ まで調べているのは、浮動小数点数の誤差を考慮して、念のため 1 多くしています。
以下が、C++プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1LL << 60)
int main()
{
ll n, m;
cin >> n >> m;
ll r = (ll)(sqrt(m) + 0.5);
ll result = INF;
for (ll a = 1; a <= r + 1; ++a) {
ll b1 = m / a;
ll b2 = m / a + 1;
if ((a <= n)&&(b1 <= n)&&(a * b1 >= m)) {
result = min(result, a * b1);
}
if ((a <= n)&&(b2 <= n)&&(a * b2 >= m)) {
result = min(result, a * b2);
}
}
if (result == INF) {
cout << -1 << endl;
} else {
cout << result << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC296D）
Python も、C++ 版をそのまま移植しました。
"""AtCoder Beginner Contest 296 D"""
import math
INF = 1 << 60
n, m = map(int, input().split())
r = int(math.sqrt(m) + 0.5)
result = INF
for a in range(1, r + 2):
b1 = m // a
b2 = m // a + 1
if a <= n and b1 <= n and a * b1 >= m:
result = min(result, a * b1)
if a <= n and b2 <= n and a * b2 >= m:
result = min(result, a * b2)
print(-1 if result == INF else result)こちらも「AC」と判定されました。
最後に
この問題は、なにかのアルゴリズムを活用して解くわけではありません。計算が持つ意味から、探索範囲を狭くすることができました。
引き続き ABC の問題を紹介していきます。
