PROBLEM LINK:
[Practice][111]
[Contest][222]
Author: [Mayank Bhandari]
Tester: [Full name][5555]
Editorialist: [Mayank Bhandari]
DIFFICULTY:
Medium
PREREQUISITES:
Priority Queue, Mathematics
Problem :
We are given p1,p2,p3,p4,p5, 5 prime numbers and we need to print the X%1000007 where X is among the first K distinct numbers of form (p1^a1)(p2^a2)(p3^a3)(p4^a4)(p5^a5) ,
where a1,a2,a3,a4 & a5 are whole numbers.
EXPLANATION:
The first such number is always 1. The basic idea is to use a priority queue. We will need to put every such element in the queue and the top element of the queue will
return the smallest number. Now we take out the top element and multiply it with all the prime numbers and put it in the queue.
The problems with direct approach for this are :
- Duplicacy
- We cannot store numbers largers than 10^18 in long long int, and if we tried using mod, then we know Mod operation can alter the comparisons among two numbers. For ex - 5 % 4 < 2 %4 , while 5 > 2 therefore we cannot use it.
First we overcome second problem by using log(X) and log(Y) to compare. We store log base 10 of the given five numbers in float and we do the addition of log in double.
The reason to use float and double is that A+B+C != C+A+B because of information loss due to precision. By taking float we ensure that this doesn’t happen.
To overcome duplicacy we can simply use map and check the value being pushed. The map will be of form map < log(X), bool(visited) > .
The priority queue will keep the pair of form pair< log(X) , mod(X) >. We take the top element print its mod and add log of p1,p2,p3,p4 and p5 respectively and
check whether a new multiple is formed or not, if yes then we push it accordingly in the map and the queue.
Therefore everytime we pop the top of the priority queue we get the log value and the mod of minimum numbers. We need to do K such pop operations to find out the required output.