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
Auto comment: topic has been updated by brucewayne123 (previous revision, new revision, compare).
B can be of order 10^18 ! generating numbers till 100000000 , wont be sufficient i guess .
Well, it was sufficient as for 11, we can have at max 200000 numbers whose largest prime is 11. So for other primes it'd be even smaller.
i am generating numbers upto the range of LLONG_MAX so i guess it was sufficient
I think the upperbound of B is unsigned long long. I got WA with long long and ACed after changing it to unsigned.
can you please share your accepted code? we cannot submit now hence i cannot check my logic! thnaks :)
Code
How to solve the triangle question ?
Did you consider the case N = 0 ? Ans is A for this case
yes i added it seperately in my code..
I implemented the solution in python to avoid overflow issues but it is not very neat.
Here is my solution: http://ideone.com/YukrSo Let me know if anything is unclear. :)
Can someone please share their solutions to the two geometry problems? Thanks!
If all the points are collinear, then only no such line will exist. other wise there will always be one such line.
I did exactly this but I don't know why I kept getting wa. :(
actually i was facing problem in handling overflows in c++.. :D