G2015 [GESP202412 二级] 寻找数字 题解

知识点：循环枚举、乘方、查找。

解题思路

预处理1到100的四次方及其底数，对每个查询寻找是否恰等于其中某个值。

为什么正确

输入上限对应底数不超过100，预处理覆盖所有候选；精确相等即可判定。

易错点

使用long long进行连乘；不存在时输出-1，不能按近似四次方根四舍五入。

复杂度

预处理O(100 log 100)，每次查询O(log 100)，空间O(100)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    map<long long,int> mp;
    for(long long i=1;i<=100;i++)mp[i*i*i*i]=i;
    int t;
    cin>>t;
    while(t--) {
        long long x;
        cin>>x;
        cout<<(mp.count(x)?mp[x]:-1)<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用6个自行生成的测试点。