/* Approach of this question */
void solve()
{
ll cnt = 0;
for (ll i = 2; i <= 31622; i++)
{
if (isPrime[i] == true)
{
ans.PB(i * i * i * i);
}
}
}
int main()
{
boost;
int T;
cin >> T;
SieveOfEratosthenes(MAX); //prime numbers
solve();
while (T–)
{
ll n;
cin >> n; // UB → upper_bound
cout << UB(ans.begin(), ans.end(), n) - ans.begin() << endl;
}
return 0;
}
why above code give AC for this problem?
The final level of i’th position would be equal to total number of it’s divisors. So we need to find all the numbers which have exactly 5 divisors. The sequence comes off as 16,81,625,… which is A030514 - OEIS . The formula mentioned here is that the nth number of this sequence is the fourth power of nth prime number. So we store all the fourth powers of all the prime numbers . The answer for each n is just the number of elements in pre-calculated array which are lesser than or equal to n.
thanks a lot…
be happy!
Welcome 