#include<iostream>
using namespace std;
typedef long long ll;
int main(){
    ll n;
    cin>>n;
    if(n<=0){
        cout<<"-1"<<endl;
        return 0;
    }
    for(ll m=1;;m++){
        ll x=1;
        bool y=false;
        for(int i=0;i<m;i++){
            if(x>n/m){
                y=true;
                break;
            }
            x*=m;
        }
        if(y || x>n)break;
        if(x==n){
            cout<<m<<endl;
            return 0;
        }
    }
    cout<<"-1"<<endl;
    return 0;
}

📝 题目大意

给定整数 $B$（$1 \le B \le 10^{18}$），判断是否存在正整数 $A$ 满足 $A^A = B$，若存在则输出 $A$，否则输出 $-1$。

💡 解题思路

1. 题目分析：$B$ 最大为 $10^{18}$，而 $A^A$ 增长极快。$15^{15} \approx 4.38 \times 10^{17} \le 10^{18}$，而 $16^{16} \approx 1.84 \times 10^{19} > 10^{18}$。因此满足条件的 $A$ 最多到 $15$，枚举范围非常小。

2. 算法推导：

   • 枚举 $A$ 从 $1$ 到 $16$（取 $16$ 作为安全上界，超出 $B$ 的会在计算中被剪枝掉）。
   • 对于每个 $A$，通过循环计算 $A^A$：初始化 val = 1，乘 $A$ 共 $A$ 次。
   • 在乘法过程中，一旦 val > B 就提前 break，避免溢出（long long 溢出会导致行为未定义）。
   • 如果最终 val == B，输出 $A$ 并结束程序。
   • 若枚举完所有 $A$ 均未匹配，输出 $-1$。

3. 边界与细节：

   • $B = 1$ 时，$1^1 = 1$，输出 $1$。
   • 乘法过程中的溢出保护至关重要：long long 最大约 $9.22 \times 10^{18}$，大于 $B$ 的上限，但直接计算 $16^{16}$ 会溢出，所以必须在每次乘法后检查 val > B 并提前跳出。
   • 题目保证 $B \ge 1$，不存在 $B = 0$ 的情况。

⏱️ 复杂度分析

• 时间复杂度：$O(1)$，枚举范围 $A \in [1, 16]$，内层最多乘 $16$ 次，常数级操作。
• 空间复杂度：$O(1)$，仅使用几个变量。

💻 标准代码 (C++)

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    long long B;
    cin >> B;
    // B ≤ 10^18，而 16^16 ≈ 1.84×10^19 > 10^18，所以 A 最多枚举到 16
    for (long long A = 1; A <= 16; A++) {
        long long val = 1;
        // 计算 A^A：将 A 自乘 A 次
        for (int i = 0; i < A; i++) {
            val *= A;
            // 若中间结果已经超过 B，提前剪枝，防止溢出
            if (val > B) break; 
        }
        if (val == B) {
            cout << A << endl;
            return 0;
        }
    }
    // 枚举完所有可能的 A 仍未找到，输出 -1
    cout << -1 << endl;
    return 0;
}