PROBLEM LINK:
Setter: Anant Kumar
Tester: अनन्य शर्मा
Editorialist: Jatin Nagpal
DIFFICULTY:
EASY-MEDIUM
PRE-REQUISITES:
Binary Search, Sorting, Sieve of Eratosthenes, Binary Exponentiation
PROBLEM:
Given a number N, you have to tell the largest number \leq N such that it can be expressed in the form a^b, where a and b are prime numbers
QUICK EXPLANATION:
Store all possible a^b where a and b are prime, in an array(vector), sort the array(vector), and search for element \leq N
EXPLANATION:
- First Apply sieve for elements ranging from 2 to \sqrt{10^{11}}, as first prime is 2, and required max of a for a^b is \sqrt{10^{11}} and for b is log(10^{11})
- Create an array, for storing all a^b, apply nested loop for a and b for all primes in increasing order, such that you break the inner loop when a^b exceeds 10^{11}
- Sort the array
- Now Start reading test cases, for each test case, apply Binary Search in the array for largest element \leq N
Time Complexity:
Let D be the number of elements in the range which is approx 3*10^4.
O(\sqrt{N} log(log(\sqrt{N})) + T log(D) )
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here
Tester’s solution can be found here
,updated now