# UVa 107

## Summary

We need to find two integer numbers N and M, where N is the number of cats inside each (non-smallest) cat's hat and M is the number of different heights in all cats.

## Explanation

• In order to solve this problem we have to find the two integers N and M. We consider the height of the first cat = A and the number of working cats = B. Using some simple math logics we can write this equation: ${\displaystyle \left({\frac {N}{N+1}}\right)^{M-1}={\frac {B}{A}}}$

• We search M in the interval (2, HighValue) and binary search for R such that ${\displaystyle R^{M-1}=B}$. We do the same for T such that ${\displaystyle T^{M-1}=A}$. If T = R + 1 then we find N = R. With the curent values of N and M we compute the output numbers:
• ${\displaystyle 1+N+N^{2}+\ldots +N^{M-2}}$ AND ${\displaystyle A\left(1+{\frac {N}{N+1}}+{\frac {N}{N+1}}^{2}+\ldots {\frac {N}{N+1}}^{M-1}\right)}$

## Gotchas

• Take care of "1 1" input case. Solving this case doesn't work with the upmentioned algorithm.
• I used HighValue = 200 in AC code.
• Take care of precision issues in the use of log().
• Consider modulus operator (%) to test A/T is an integer or not in integer-only implementation.

## Input

1 1
216 125
5764801 1679616
1024 243
2 1
4 1
1024 1
371293 248832
11 10
1048576 59049
483736625 481890304
125 64
64 1
81 64
0 0


## Output

0 1
31 671
335923 30275911
121 3367
1 3
2 7
10 2047
22621 1840825
1 21
29524 4017157
615441 1931252289
21 369
6 127
9 217