#include <iostream>

using namespace std;

const int MAXN = 1000;
const int oo = INT_MAX;

int m, n;
int F[MAXN][MAXN];
int H[MAXN][MAXN];

void Nhap() {
    cout << "Nhap so hang: "; cin >> m;
    cout << "Nhap so cot: "; cin >> n;
}

void QHD() {
    int i, j, c, h;

    for (i=1; i<=m; i++) {
        for (j=1; j<=n; j++) {
            if (i == j) F[i][j] = 1;
                else if (i > j) F[i][j] = F[j][i];
                    else if (j%i == 0) F[i][j] = j/i;
                        else { // j > i va j khong chia het cho i
                            F[i][j] = +oo;
                            for (c=1; c<=j/2; c++)
                                if (F[i][j] > F[i][c] + F[i][j-c]) {
                                    F[i][j] = F[i][c] + F[i][j-c];
                                    H[i][j] = +c;
                                }


                            for (h=1; h<=i/2; h++)
                                if (F[i][j] > F[h][j] + F[i-h][j]) {
                                        F[i][j] = F[h][j] + F[i-h][j];
                                        H[i][j] = -h;
                                }
                        }
        }
    }
}

void TruyVet(int i, int j) {
    if (i == j) {
        cout << i << "   ";
        return;
    }

    if (i > j) {
        TruyVet(j, i);
        return;
    }

    // i < j
    int k;
    if (j%i == 0) {
        for (k=1; k<=j/i; k++) cout << i << "   ";
        return;
    }

    int c, h;
    if (H[i][j] > 0) {
        c = H[i][j];
        TruyVet(i, c);
        TruyVet(i, j-c);
        return;
    }

    // H[i][j] < 0
    h = -H[i][j];
    TruyVet(h, j);
    TruyVet(i-h, j);
    return;
}

void KQ() {
    cout << "So it nhat cac hinh vuong la: " << F[m][n] << endl;
}

int main(){
    Nhap();
    QHD();
    KQ();
    cout << "Cach chia la: " << endl;
    TruyVet(m, n);

}