I've seen this problem on an algorithms competition and although there is an explanation on the website, I couldn't understand it.
The abridged problem statement is as follows:
Suppose you have two chocolate bars, of sizes $a_1$ x $b_1$ and $a_2$ x $b_2$ (chocolate squares).
You want to make both bars have the same number of chocolate squares and for that you are allowed to do the following moves:
- Chop half of a bar (either horizontaly or verticaly) and throw it away
- Chop a third of a bar (either horizontaly or verticaly) and throw it away
(Both moves can be done in any of the bars and as much as we want, as long as the sizes are kept with integer values).
Given that, the questions are:
Is it possible to make both bars have the same number of squares?
If yes, what's the minimum number of moves required?
I'm interested not only in the answer itself, but also in a proof of why it works and the reasoning/thought proccess behind it (more interested in the proof and thought proccess, actually :) ).
Edit: Added that the sizes must remain with integer values for some clarification.
The first thing you have to realize is that the only thing that matters is the areas of each of the bars.
So let $A$ and $B$ be those areas. Now let $A$ have canonical prime factorization $2^{a_2}\cdot3^{a_3}\dots \cdot p_n^{a_n}$ and let $B$ have canonical factorization $2^{b_2}\cdot3^{b_3}\dots p_n^{b_n}$ . A necessary condition for being able to pass from area $A$ to area $B$ is that they have the same canonical factorization except possibly for the primes $2$ and $3$. This should be the first thing you check.
After checking this, if they do have the same prime factorization proceed to making their powers of $3$ equal. suppose $|a_3-b_3=k|$, then this is going to take $k$ bites, you are going to have to make the bar with the larger power of $3$ smaller by chopping of a third. This is going to take $k$ bites. And it is going to increase the power of two of that bar by $k$.
So suppose $A$ had a larger power of $3$. Then after $k$ bites the power of $2$ is going to be $2^{a_2+k}$. But you will have that bars $A$ and $B$ will coincide in all prime powers except for possibly $2$.
These powers will be $2^{a_2+k}$ and $2^{b_2}$. To fix this you need $|a_2+k-b_2|$ bites.
Knowing that the sides are under $10^9$ might be helpful, this is because you can find the prime decomposition of each of the sides first. pass the numbers into arrays with the prime exponents, and multiplying two numbers in their prime exponent form is just adding the exponents, from here you get $A$ and $B$ in prime exponent form and first check if the arrays coincide in all except for possibly the first two entries. (although I don't know if 1 second is enough time to factor numbers so large). But if you do manage to factor the numbers the rest is really easy.