Nỗ lực ít nhất có thể (The Least Possible Effort)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Trong bài toán hành trình của quân mã, ta chọn một ô xuất phát rồi di chuyển quân mã sao cho mỗi ô của bàn cờ được thăm đúng một lần.

Nếu hai ô xuất phát biến đổi được thành nhau bằng một phép đối xứng của toàn bộ bàn cờ, việc kiểm tra một ô cũng đại diện cho ô còn lại: phản xạ hoặc quay một hành trình hợp lệ sẽ tạo ra một hành trình hợp lệ tương ứng.

Cho bàn cờ hình chữ nhật gồm $n$ hàng và $m$ cột. Hãy tìm số lượng ô xuất phát ít nhất cần kiểm tra để đại diện cho mọi lớp ô tương đương theo các phép đối xứng của bàn cờ.

Input

Một dòng chứa hai số nguyên $n$ và $m$, lần lượt là số hàng và số cột.

Output

In số lượng vị trí xuất phát ít nhất cần kiểm tra.

Subtask

• Subtask 1 (20%): $n\ne m$ và cả $n,m$ đều chẵn.
• Subtask 2 (30%): $n\ne m$ và có ít nhất một kích thước lẻ.
• Subtask 3 (50%): Đầy đủ: $6\le n,m\le10000$; có thể có $n=m$.

Ví dụ

Input

6 9

Output

15

Giải thích

Đánh số hàng từ $1$ đến $6$. Phản xạ theo trục ngang ghép các hàng thành ba cặp (1,6), (2,5), (3,4).

Đánh số cột từ $1$ đến $9$. Phản xạ theo trục dọc tạo năm nhóm (1,9), (2,8), (3,7), (4,6) và {5}.

Bàn cờ có kích thước $6\times9$, nên phép quay $90^\circ$ không thể hoán đổi vai trò của hàng và cột. Mỗi lớp vị trí được xác định bởi một nhóm hàng và một nhóm cột, nên có

lớp cần đại diện. Vì vậy chương trình in 15.