Dễ thấy ở mỗi lần cắt, cạnh của hình vuông lớn nhất có thể cắt được là chiều rộng của mảnh giấy. Số lượng hình vuông ở mỗi lần cắt là $\lfloor \frac{M}{N} \rfloor $ với $M, N$ lần lượt là chiều dài và chiều rộng của mảnh giấy ở lần cắt đang xét. Ta tiếp tục xét cho tới khi chiều dài hoặc chiều rộng của mảnh giấy bằng $0$, tức mảnh giấy không thể cắt được nữa.

Code tham khảo

void solve(){
    ans = 0;
    while (m > 0 && n > 0){
        if (m < n) swap(m, n);
        ans += m/n;
        m %= n;
    }
    cout << ans;
}

Độ phức tạp thuật toán: $\mathcal{O}(\log_2(m+n))$.