UVA 10970 Big Chocolate ( 數學水題 )

UVa Online Judge
給一個 n * m的巧克力，問最少要切幾刀才能全部變成 1 * 1的巧克力，一次只能切在一塊的整數線上。
直覺上把巧克力變成 n條 m個巧克力的條或 m條 n個巧克力的條不會比縱橫亂切差，簡化一下代數又發現這兩種都必須要切 n * m - 1次。。如果有人知道比較嚴謹的證明請留言告訴我，謝謝。
追記：數學家的22個思考工具裡有提到一模一樣的題目，把原本的巧克力視為一堆，因為每次分割必然恰好增加一堆，且全部各自變成1*1就是要成為n * m個堆，顯然必須要分割n * m - 1次。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300 + 2;
const int MAXM = 300 + 2;

int main(){
    int n, m;
    while( scanf("%d%d", &n, &m) == 2 ){
        printf("%d\n", n * m - 1);
    }
    return 0;
}