CodeForces490D Chocolate

题目：

Description
Polycarpus likes giving presents to Paraskevi. He has bought two chocolate bars, each of them has the shape of a segmented rectangle. The first bar is a1× b1 segments large and the second one is a2× b2 segments large.
Polycarpus wants to give Paraskevi one of the bars at the lunch break and eat the other one himself. Besides, he wants to show that Polycarpus's mind and Paraskevi's beauty are equally matched, so the two bars must have the same number of squares.
To make the bars have the same number of squares, Polycarpus eats a little piece of chocolate each minute. Each minute he does the following:
he either breaks one bar exactly in half (vertically or horizontally) and eats exactly a half of the bar,
or he chips of exactly one third of a bar (vertically or horizontally) and eats exactly a third of the bar.
In the first case he is left with a half, of the bar and in the second case he is left with two thirds of the bar.
Both variants aren't always possible, and sometimes Polycarpus cannot chip off a half nor a third. For example, if the bar is 16 × 23, then Polycarpus can chip off a half, but not a third. If the bar is 20 × 18, then Polycarpus can chip off both a half and a third. If the bar is 5 × 7, then Polycarpus cannot chip off a half nor a third.
What is the minimum number of minutes Polycarpus needs to make two bars consist of the same number of squares? Find not only the required minimum number of minutes, but also the possible sizes of the bars after the process.
Input
The first line of the input contains integers a1, b1 (1 ≤ a1, b1≤ 10的9次方) — the initial sizes of the first chocolate bar. The second line of the input contains integers a2, b2(1 ≤ a2, b2 ≤ 10的9次方) — the initial sizes of the second bar.
You can use the data of type int64 (in Pascal), long long (in С++), long (in Java) to process large integers (exceeding 2的31次方- 1).
Output
In the first line print m — the sought minimum number of minutes. In the second and third line print the possible sizes of the bars after they are leveled in m minutes. Print the sizes using the format identical to the input format. Print the sizes (the numbers in the printed pairs) in any order. The second line must correspond to the first bar and the third line must correspond to the second bar. If there are multiple solutions, print any of them.
If there is no solution, print a single line with integer -1.
Sample Input
Input
2 6
2 3
Output
1
1 6
2 3
Input
36 5
10 16
Output
3
16 5
5 16
Input
3 5
2 1
Output
-1

题目大意：
有两个矩形，它们的长和宽分别为a1, b1, a2, b2（均为整数），现在可以通过两种方式改变两个矩形的长或宽（可以改动任何一条边，但之后仍然是个矩形且边依旧都是整数）。
可以将某条边变为原来的1/2.
可以将某条边变为原来的2/3.
问至少要经多少步骤才能让两个矩形的面积相等（若有则输出所需时间以及最终结果，若没有则输出-1）。

一开始我没有想到好的方法，直到看了某些大神的博客后才略微有思路。

首先要解决的是是否存在一种方法让两个矩形最后的面积相等。由于这两种方法要么除以2， 要么除以3乘以2（但要保证之后的结果依旧是整数），因此我们可以先将它们的面积求出来，然后除去它们的因子2和3，看最后的面积能否相等，如果相等则有可能，反之没有。

如果有可能，则求出结果。我们可以在之前去除因子2和3的过程中统计一下两个面积中包含因子2和3的个数。因为要求出最小的执行步骤数，因此我们可以先判断两个面积中谁包含的因子3的个数最多（因为除以一个3会乘以一个2，导致包含2的个数不确定，从而无法得到最佳答案），谁包含的3多就处理谁，然后将长变为2/3，无法得到整数了就处理宽（但要注意除以3的个数）。然后依此对2进行处理即可。

参考代码：

#if __cplusplus < 201103L
    #error "please use C++11 implementations"
#endif
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long ll;

ll mintime(ll &a1, ll &b1, ll &a2, ll &b2) {
    ll area1, area2;
    area1 = a1 * b1;
    area2 = a2 * b2;
    ll a = area1, b = area2;
    ll n2 = 0, n3 = 0, m2 = 0, m3 = 0;//第一个和第二个中分别包含素因子2和3的个数;
    while (a % 2 == 0 || a % 3 == 0) {
        if (a % 2 == 0) {
            a = a / 2;
            ++n2;
        }
        else {
            a = a / 3;
            ++n3;
        }
    }
    while (b % 2 == 0 || b % 3 == 0) {
        if (b % 2 == 0) {
            b = b / 2;
            ++m2;
        }
        else {
            b = b / 3;
            ++m3;
        }
    }
    if (a != b) return -1;
    else {
        ll ans = abs(n3 - m3);//两个面积之间相差的素因子3的个数;
        if (m3 > n3) {//乘以三分之二: 扣掉3在补回2;
            m3 -= ans;
            m2 += ans;
            ll ans1 = ans;
            while (a2 % 3 == 0 && ans1) {
                a2 = a2 / 3 * 2;//乘以三分之二;
                --ans1;
            }
            while (b2 % 3 == 0 && ans1) {
                b2 = b2 / 3 * 2;
                --ans1;
            }
        }
        else {
            n3 -= ans;
            n2 += ans;
            ll ans1 = ans;
            while (a1 % 3 == 0 && ans1) {
                a1 = a1 / 3 * 2;
                --ans1;
            }
            while (b1 % 3 == 0 && ans1) {
                b1 = b1 / 3 * 2;
                --ans1;
            }
        }
        ans += abs(m2 - n2);//相差因子2的个数;     
        if (m2 > n2) {
            ll ans1 = abs(m2 - n2);
            while (a2 % 2 == 0 && ans1) {
                a2 = a2 / 2;
                --ans1;
            }
            while (b2 % 2 == 0 && ans1) {
                b2 = b2 / 2;
                --ans1;
            } 
        }
        else {
            ll ans1 = abs(m2 - n2);
            while (a1 % 2 == 0 && ans1) {
                a1 = a1 / 2;
                --ans1;
            }
            while (b1 % 2 == 0 && ans1) {
                b1 = b1 / 2;
                --ans1;
            }
        }
        return ans;
    }   
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ll a1, b1, a2, b2;
    cin >> a1 >> b1 >> a2 >> b2;
    ll ans = mintime(a1, b1, a2, b2);
    cout << ans << endl;
    if (ans != -1)
        cout << a1 << " " << b1 << endl << a2 << " " << b2 << endl;
    return 0;
}

理解还不是很透彻（毕竟不是自己想出来的），欢迎大家提出意见。