XPONENT Editorial

editorial
1

Problem Link

** PREREQUISITES**
OBSERVATION, MATH, PRECOMPUTATION

EXPLANATION:
We need to find if a given N can be expressed as x^y (x>=1 and y>1) the range of N is [1,10^9]
So we can just precalculate the powers of all numbers from [2, sqrt(10^9)] that are in range of 10^9 and check if the given number is present in that list.

Code:

#include<bits/stdc++.h>
using namespace std;
unordered_set<int> ans;
void pre()
{
    long maxi=(1e9);
    ans.insert(1);
    for(long i=2;i*i<=maxi;i++)
    {
        long val=i*i;
        while(val<=maxi)
        {
            ans.insert(val);
            val*=i;
        }
    }
}
void solve()
{
    int n;
    cin>>n;
    if(ans.find(n)!=ans.end())
    {
        cout<<"Yes\n";
    }
    else
    {
        cout<<"No\n";
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    pre();
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}