 # Editorial-MATPH

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

4 Likes

Shouldn’t the time complexity be O(√N log(log(√N))+T log(D) )?

Yup ,updated now

Use scanf and printf instead of cin and cout if you are getting TLE in some subtasks

I think fast io with cin, cout works fine.