主題
題目連結：
題目大意：
輸入有好幾筆測試資料（＜ 900000 筆）。每筆佔一列，每列給定兩正整數 N 、 M （N 、 M ≦ 10000），代表有一 N 列 M 行個單位格子形成的矩形。
求這個矩形裡有多少個正方形以及長方形（在此特指鄰邊不相等的矩形）？
範例輸入：
1 2
3 4
5 6
範例輸出：
2 1
20 40
70 245
解題思維：
我們先求給定的 N × M 個格子中可以形成幾個矩形。用簡單的排列組合可知：從 N ＋ 1 條邊中挑兩個形成矩形的上下側；再從 M ＋ 1 條邊挑出兩個形成矩形的左右兩邊。因此總數量為
N × （N ＋ 1） × M × （M ＋ 1）
接著來算正方形的數量：
假設 N ＜ M ，我們可以看到
1 × 1 的正方形有 N × M 個、
2 × 2 的正方形有 （N － 1） × （M － 1） 個、
3 × 3 的正方形有 （N － 2） × （M － 2） 個、
……
i × i 的正方形有 （N － i ＋ 1） × （M － i ＋ 1） 個、
……
N × N 的正方形有 M － N ＋ 1 個
因此總共為
Σ （N － i ＋ 1） × （M － i ＋ 1） ，其中 1 ≦ i ≦ N 。
展開上式可得
Σ N × M ＋ N ＋ M ＋ 1 － i × （N ＋ M ＋ 2） － i ^ 2
繼續簡化到最後可得
N × （N ＋ 1） × （3M － N ＋ 1） ÷ 6
上式正是正方形數量的公式（前提是 N ＜ M）
則題目所求的長方形也呼之欲出，即矩形數量 － 正方形數量。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
