Editorial-MATPH


#1

PROBLEM LINK:

Contest
Practice

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


#2

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


#3

Yup :sweat_smile: ,updated now