約数列挙!!!
問題概要
正の整数 が与えられる。
を満たすような正の整数 の組をすべて考えたときの、 の最小値を求めよ。
制約
考えたこと
これはまさに約数列挙の問題!!!
以下の記事の「3. 約数列挙」のところで、本質的に同じ問題の解説を行なっている。
具体的には次のようにすればよい。
- と割っていく (ただし、 の範囲まででよい)
- が を割り切るとき、 とする
- そのような の最小値を求める
基本的には試し割りしていく全探索解法だが、 の範囲でよい、というのがポイントになる。計算量は 。
コード
#include <bits/stdc++.h> using namespace std; int main() { long long N; cin >> N; long long res = N + 1 - 2; // (a, b) = (1, N) for (long long a = 1; a * a <= N; ++a) { if (N % a == 0) res = min(res, a + N/a - 2); } cout << res << endl; }