Tác giả: Nguyễn Hữu Nhật Quang Solution: Mai Ngọc Phú

Nhận xét: thứ tự xếp các khối gỗ không quan trọng ~\rightarrow~ ta chỉ quan tâm có ~x \le n~ khối gỗ độ cao ~a~ và ~y \le m~ khối gỗ độ cao ~b~.

Đặt ~a' = \frac{a}{gcd (a, b)}, b'= \frac{b}{gcd (a, b)}~. Dễ thấy ~a \times b' = b \times a'~. Do đó chúng ta có thể thay ~a'~ khối gỗ độ cao ~b~ thành ~b'~ khối gỗ độ cao ~a~.

Chiều cao một cột gỗ có thể tính theo công thức: $$h = ax \times by$$ Với ~0 \le x \le n~ và ~0 \le y \le m~ dễ thấy được số lượng ~h~ sinh ra là ~(m+1)\times(n+1)~

Tuy nhiên ta cần tìm số giá trị ~h~ khác nhau nên phải trừ đi số lượng ~h~ trùng nhau

Ta có: $$h = ax \times by$$$$\leftrightarrow h=ax\times by-k\times a\times b' +k \times a'\times b$$$$\leftrightarrow h=a(x-kb')+b(y+ka')$$

• ~k\in N~ , ~0\le x-kb'~ , ~y+ka'\le m~

Như vậy với ~1~ giá trị ~h~ có nghiệm ~(x,y)~ với ~n-b'+1 \le x \le n~ hoặc ~0 \le y \le a'-1~ sẽ luôn có ít nhất một nghiệm ~(x,y)~ với ~0 \le x \le n-b'~ và ~a'+1 \le y \le m~ ~(~ nếu ~0 \le n-b'~ và ~a'+1\le m~~)~

Suy ra số lượng ~h~ trùng nhau là: ~max((n-b'+1),0)\times max((m-a'+1),0)~

Kết quả cần tìm là: ~(m+1)\times(n+1)-max((n-b'+1),0)\times max((m-a'+1),0) -1~ ~(~trừ thêm ~1~ vì ~x~, ~y~ không đồng thời bằng ~0)~