まず \(A=1\) が解になるのは \(B=1\) のときのみなので予め処理しておきます．

\(A=2,3,\dots\) に対し，\(B\) を \(A\) で割り切れるだけ割ります．\(B\) が \(A\) で割り切れた回数を \(X\)，\(B\) を \(A\) で \(X\) 回割った値を \(Y\) とすれば \(B=A^XY\) であり，\(Y\) は \(A\) で割り切れないので，\(A^A=B\) であるための必要十分条件は \(X=A,Y=1\) であることがわかります．

\(X,Y\) は実際に割れば各 \(A\) についてそれぞれ計算量 \(O(\log B)\) で求められます．

なお公式解説では実験した上で \(A\) の上限として \(15\) を取っていますが，この方針であればもう少し雑に評価して \(15\) より大きくとっても 64 bit 整数で問題なく動きます．

#include <iostream>
using namespace std;

void solve() {
  long long B;
  cin >> B;
  if (B == 1) {
    cout << 1 << endl;
    return;
  }
  for (int A = 2; A <= 20; A++) {
    int x = 0;
    long long y = B;
    while (y % A == 0) x++, y /= A;
    if (x == A && y == 1) {
      cout << A << endl;
      return;
    }
  }
  cout << "-1" << endl;
}

int main() {
  solve();
}