Pizza slicing

Tonight you will be at one of the regular GAUSS sky observation nights, and as always there’s free pizza. The $N$ participants have ordered a single giant $A\times B$ rectangular pizza that you will have to share between you. To break the monotony of looking at differently sized spherical objects all evening, you have all decided to only eat identically sized square pieces of pizza. All the participants are hungry, so they will all need at least one slice each. Additionally, it would be an awful shame to have pizza left over, so all of it must be used for the identical squares. You brought your very dearly held pizza slicer, and because it is so precious to you you would like to carry out as few straight slicing cuts as possible. You can move the pieces of pizza around on your very large table holding your very large pizza, so that multiple pieces can be sliced in the same cut.


The input contains a single line: $N$ ($2 \le N \le 10^{18}$), $A$ and $B$ ($1 \le A, B \le 10^{18}$) separated by spaces.


Print a single number, the least number of cuts required to split the pizza into at least $N$ identically sized square pieces.

Sample Input 1 Sample Output 1
5 2 3
Sample Input 2 Sample Output 2
15 70 20
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 6.8hard
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in