Tìm các cách cắt khác nhau của hình chữ nhật

[bubabua (Huy Quang)]

Hải có một tờ giấy kích thước (m x n) . Hải muốn cắt tờ giấy đó thành các hình chữ nhật có diện tích bằng nhau. Hãy tìm và đưa ra các cách cắt khác nhau.

(Hai cách cắt khác nhau nếu diện tích của các hình chữ nhật sau khi cắt của mỗi trường hợp là khác nhau).

Ví dụ:

• Với m=2, n=3 , thì countHowToCutPaper(m,n) = 4.
  Giải thích: có 4 cách cắt đó là:
  • Cắt thành 6 hình có diện tích 1.
  • Cắt thành 3 hình có diện tích 2.
  • Cắt thành 2 hình có diện tích 3.
  • Cắt thành 1 hình có diện tích 6.

Ai giúp e thuật toán bài này với ạ

[rogp10]

Có vẻ không khác gì bài đếm số ước của m*n vì diện tích phải chia hết cho m*n.

[bubabua (Huy Quang)]

E cũng làm đếm ước nhưng nó ko ra, tại số lớn quá nên nó mất nhiều thời gian và vượt quá thời gian quy định

[rogp10]

Bạn có thể đếm cho m riêng và n riêng, bằng cách đưa về hai số nguyên tố cùng nhau

Tìm cặp số bạn bè (amicable pairs)

Để mình đọc lại đã rồi xong. Cách 1: Cho m1, m2 là ước của m; n1, n2 là ước của n. Nếu m1n1 = m2n2 thì m1/n2 = m2/n1 Vì nếu UCLN(m1, n2) != 1 thì mâu thuẫn, nên hai phân số đều tối giản. Vậy tử bằng tử, mẫu bằng mẫu, suy ra đpcm. Cách 2: Với m, n nguyên tố cùng nhau thì m’ | m => m’ | mn n’ | n => n’ | mn m’, n’ | mn <=> BCNN(m’, n’) | mn (định nghĩa) Nếu UCLN(m’, n’) != 1 thì UCLN(m, n) != 1 do tích = UCLN * BCNN nên tìm được song ánh {ước của m} x {ước của n} -> {ước…