ATOMS - Atoms in the Lab

Mr. Yagami is a scientist in the Bhabha Atomic Research Centre. They are conducting a lab experiment on nuclear fission. In nuclear fission, one atom breaks into more than one atom of the same type.

Initially, there are N atoms in the lab. Starting from now (t=0), after each second, every atom will break into K atoms of the same type. They don’t want the number of atoms to exceed M, so they have to stop the reaction at some time t=T. Can you find this value T for Mr. Yagami.

Input Format:

First line contains P, the number of test cases. Next P lines contain three integers each. These three integers represent the values of N, K and M respectively.

Output Format:

For each test case print the time at which the reaction will have to be stopped.


1 ≤ P ≤ 10^4
2 ≤ N, K, M ≤ 10^18

Sample Input:

2 2 7
2 2 8

Sample Output:



1st test case:
at t=1, number of atoms=4
at t=2, number of atoms will be 8.
So reaction has to be stopped at t=1.

2nd test case:
at t=1, number of atoms=4
at t=2, number of atoms will be 8.
at t=3, number of atoms will be 16.

Problem Setter: Lalit Kundu

hide comments
mpride44: 2017-12-31 17:01:35

beauty of ques is---range of double(15 digits) ,long double(15 digits),float(7 digits)
so u cant store 10^18 in u hv to take unsigned long long int then a proper algorithm take u to ac..

shabana_ali: 2017-10-15 11:57:30

brute force users, use long double

vishwanath_26: 2017-08-10 16:34:12

Simple one! AC in one go!!!

rohit659: 2017-06-29 15:03:26

Take Care of m<n.
Costed me 2 WA.
Finally AC!!!

cj23897: 2017-06-27 08:12:03

Brute force users, use unsigned long long

vettyvignesh: 2017-06-23 13:57:57

For those who are using log, make sure to take care of the cases where k is 1.

Last edit: 2017-06-23 13:58:14
ak_cruiser: 2017-06-18 00:57:55

long long int is giving tle because of the fact that it uses more bits to store ...use double and get ac....i also got a tle

mark42: 2017-06-11 22:03:04


arvind002: 2017-06-01 14:40:09

Same code gave me TLE when i used long long but accepted when i used long Double in C++.

Last edit: 2017-06-01 14:40:43
horizon121: 2017-05-25 20:09:26

for some reason log was giving me some error so just used basic math :)

Added by:darkshadows
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)