Closest Multiplicative Disassembly

$ab=N$ を $b=\frac Na$ と変形することで $a$ から $b$ が一意に定まることが分かります。
よって、答えとなる $a$ を探すことを考えます。

$a^2\le ab=N$ より、$a$ が正整数であることも併せて $1\le a^2\le N$ の範囲を探索すればいいことが分かります。

後はある $a$ について、$b=\frac Na$ が正整数になればよいです。つまり $a$ が $N$ を割り切るかどうかを判定すればいいです。

以上を適切に実装することで、本問題を $O(\sqrt N)$ で解くことができました。

実装例（C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16#include <bits/stdc++.h>
using namespace std;
int main()
{
  long long N;
  cin >> N;

  long long a = 1, A;
  while (a * a <= N)
  {
    if (N % a == 0)
      A = a;
    a++;
  }
  cout << A << " " << N / A << endl;
}