算法題：用相同矩形磚拼成最小正方形——最小公倍數應用

問題描述

給定矩形磚尺寸 W × H，所有磚相同且不可切割，需拼成一個正方形，求所需最少磚塊數。

數學模型

正方形邊長必須是 W 和 H 的公倍數，最小邊長為 LCM(W, H)。

所需磚數 = (LCM/W) * (LCM/H) = LCM² / (W*H)。

樣例驗證

輸入: 2 3
LCM(2,3)=6
磚數 = (6/2)*(6/3) = 3*2 = 6  → 輸出 6

輸入: 1 2
LCM(1,2)=2
磚數 = (2/1)*(2/2) = 2*1 = 2  → 輸出 2

C++ 實現

#include 
using namespace std;
long long gcd(long long a, long long b) { return b?gcd(b,a%b):a; }
int main() {
    long long W, H;
    while (cin >> W >> H) {
        if (W==0 && H==0) break;
        long long lcm = W / gcd(W,H) * H;
        cout << (lcm/W) * (lcm/H) << "\n";
    }
    return 0;
}

參考

UVa 10070 - Tiles of Tetris, NOT! 解析