hi everyone! i was trying this problem HENRY:-↵
Henry and Lost Ranges↵
↵
Henry is a curious little boy. He likes to play around with numbers. One day, he defined a↵
fun ction f for natural numbers such that:↵
f(X) = largest prime factor of X , where X > 1↵
For example: f(2) = 2↵
↵
f(3) = 3↵
↵
f(75) = 5↵
↵
Now, Henry selected two integers A and B ( A ≤ B ) and counted all numbers X between A and B↵
(both inclusive) such that f(X) = K . He found out that there are N such numbers.↵
After that Henry went for playing. When he returned home, he found out that he had forgotten↵
the upper limit of range i.e. the integer B . However, he remembers all other numbers i.e. A , K↵
and N .↵
↵
Henry wants to find out B as soon as possible. Can you help him finding it ?↵
↵
Note:↵
↵
● If there are multiple possible values of B , output the least value out of those.↵
↵
● It is assured that the input will be in such a way that final value of B will be within the↵
range of long long int .↵
↵
Input↵
↵
First line of input contains T , the number of test cases.↵
The only line of each test case contains three integers A , K and N .↵
↵
Output↵
↵
For each test case, output a single line containing the integer B .↵
↵
Constraints↵
↵
● 1 ≤ T ≤ 5↵
↵
● 2 ≤ A ≤ 10 9↵
↵
● 2 ≤ K ≤ 11 and K is a prime number↵
↵
● 0 ≤ N ≤ 152319↵
↵
Example↵
↵
Input:↵
↵
5↵
3 2 4↵
↵
5 3 4↵
↵
4 5 4↵
↵
5 7 4↵
↵
3 11 4↵
↵
Output:↵
↵
32↵
↵
18↵
↵
20↵
↵
28↵
↵
44↵
↵
Explanation↵
↵
In the first case, least value of B such that there are exactly 4 numbers having largest prime↵
factor as 2 in range [3,B] will be 32 (the 4 numbers are 4, 8, 16, 32 ).↵
↵
In the second case, least value of B such that there are exactly 4 numbers having largest prime↵
factor as 3 in range [5,B] will be 18 (the 4 numbers are 6, 9, 12, 18 ).↵
↵
In the third case, least value of B such that there are exactly 4 numbers having largest prime↵
factor as 5 in range [4,B] will be 20 (the 4 numbers are 5, 10, 15, 20 ).↵
↵
In the fourth case, least value of B such that there are exactly 4 numbers having largest prime↵
factor as 7 in range [5,B] will be 28 (the 4 numbers are 7, 14, 21, 28 ).↵
↵
In the fifth case, least value of B such that there are exactly 4 numbers having largest prime↵
factor as 11 in range [3,B] will be 44 (the 4 numbers are 11, 22, 33, 44 ).↵
↵
↵
my solution:- http://pastebin.com/VccNHSwz↵
since k is <= 11 hence we have primes 2,3,5,7,11 only.. for a particular k i need to check only the numbers formed with combinations of all prime numbers<=k for example.. if k=5 then 2^a*3^b*5^c where c>=1 and a>=0 and b>=0.. so i precomputed all such numbers for all k in <=100000000↵
then i applied lower_bound to find the least b↵
i am getting wrong answer although i think i have handled overflows correctly! please someone help me understand my mistake!↵
PS:- code is lengthy because but very easy to understand↵
Henry and Lost Ranges↵
↵
Henry is a curious little boy. He likes to play around with numbers. One day, he defined a↵
fun ction f for natural numbers such that:↵
f(X) = largest prime factor of X , where X > 1↵
For example: f(2) = 2↵
↵
f(3) = 3↵
↵
f(75) = 5↵
↵
Now, Henry selected two integers A and B ( A ≤ B ) and counted all numbers X between A and B↵
(both inclusive) such that f(X) = K . He found out that there are N such numbers.↵
After that Henry went for playing. When he returned home, he found out that he had forgotten↵
the upper limit of range i.e. the integer B . However, he remembers all other numbers i.e. A , K↵
and N .↵
↵
Henry wants to find out B as soon as possible. Can you help him finding it ?↵
↵
Note:↵
↵
● If there are multiple possible values of B , output the least value out of those.↵
↵
● It is assured that the input will be in such a way that final value of B will be within the↵
range of long long int .↵
↵
Input↵
↵
First line of input contains T , the number of test cases.↵
The only line of each test case contains three integers A , K and N .↵
↵
Output↵
↵
For each test case, output a single line containing the integer B .↵
↵
Constraints↵
↵
● 1 ≤ T ≤ 5↵
↵
● 2 ≤ A ≤ 10 9↵
↵
● 2 ≤ K ≤ 11 and K is a prime number↵
↵
● 0 ≤ N ≤ 152319↵
↵
Example↵
↵
Input:↵
↵
5↵
3 2 4↵
↵
5 3 4↵
↵
4 5 4↵
↵
5 7 4↵
↵
3 11 4↵
↵
Output:↵
↵
32↵
↵
18↵
↵
20↵
↵
28↵
↵
44↵
↵
Explanation↵
↵
In the first case, least value of B such that there are exactly 4 numbers having largest prime↵
factor as 2 in range [3,B] will be 32 (the 4 numbers are 4, 8, 16, 32 ).↵
↵
In the second case, least value of B such that there are exactly 4 numbers having largest prime↵
factor as 3 in range [5,B] will be 18 (the 4 numbers are 6, 9, 12, 18 ).↵
↵
In the third case, least value of B such that there are exactly 4 numbers having largest prime↵
factor as 5 in range [4,B] will be 20 (the 4 numbers are 5, 10, 15, 20 ).↵
↵
In the fourth case, least value of B such that there are exactly 4 numbers having largest prime↵
factor as 7 in range [5,B] will be 28 (the 4 numbers are 7, 14, 21, 28 ).↵
↵
In the fifth case, least value of B such that there are exactly 4 numbers having largest prime↵
factor as 11 in range [3,B] will be 44 (the 4 numbers are 11, 22, 33, 44 ).↵
↵
↵
my solution:- http://pastebin.com/VccNHSwz↵
since k is <= 11 hence we have primes 2,3,5,7,11 only.. for a particular k i need to check only the numbers formed with combinations of all prime numbers<=k for example.. if k=5 then 2^a*3^b*5^c where c>=1 and a>=0 and b>=0.. so i precomputed all such numbers for all k in <=100000000↵
then i applied lower_bound to find the least b↵
i am getting wrong answer although i think i have handled overflows correctly! please someone help me understand my mistake!↵
PS:- code is lengthy because but very easy to understand↵
