\(2 \leq X \leq 3 \times 10^{18}\) を満たす整数 \(X\) であって、\(N! = X\) を満たす整数 \(N\) が存在するような \(X\) の最大値は \(2432902008176640000 (=20!)\) です。また、\(2 \leq X\) であるため、\(2 \leq N\) を満たします。

よって、以下のような方法でfor文等を用いて答えを求めることができます。

• \(i=2,\ldots,20\) について以下の操作を順に行う
  • \(i!\) を求めるための変数 \(f\) を用意する。最初に \(f\) は \(1\) で初期化されている。
  • \(j=1,\ldots i\) について以下の操作を順に行う
    • \(f\) に \(j\) を掛ける
  • \(f\) と \(X\) が等しいとき、\(i\) を出力する

答えとしてありえる最大値を \(N\) とするとこれは時間計算量 \(O(N^2)\) となります。今回は \(N =20\) であるため、十分高速に求められます。実装の際は32bit整数で計算するとオーバーフローすることに注意してください。

また、\(i!\) の計算を \(i\) が小さい順に求めていくことで、全体で \(O(N)\) 時間で求めることも可能です。

実装例(C++):

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

int main() {
    long long x;
    cin >> x;
    for (int i = 2; i <= 20; ++i) {
        long long f = 1;
        for (int j = 1; j <= i; ++j) {
            f *= j;
        }
        if (f == x) {
            cout << i << endl;
        }
    }
}