UVa12149 - Feynman( 數論 Math theorm )

題目大意

費曼在筆記中夾著餐巾紙，上面寫到在一個 n * n 的正方形中，裡面可以有多少種不同的正方形。
舉例：在 2 * 2 的正方形中，總共會有 5 種不同的正方形

觀念重點

• 推算出 n 的正方形有多少種正方形
• 再將這推算變成一數學公式

分析

大難題XD，對於數學底子不好的我來說完全沒有辦法克服這題阿，我就像笨蛋一樣，嗚嗚。看了詳解並且詳細推了公式之後才了解一些。

想出其他測試資料

一開始要先稍微去推導其他例子，也就是除了範例以外我們再去想想在 n = 多少時會有多少正方形。

• n = 2 ，此時總共有 5 個正方形
• n = 3 ，此時總共有 14 個正方形
• n = 4 ，此時總共有 30 個正方形
• 不要問我怎麼算的，手畫真的很累..

歸納

如果真的有努力畫到 n = 4，那應該可以歸納出一個邏輯

• 正方形邊長為 1
  假如有一個 n 邊長的正方形，那他一定會有 n * n 個邊長為 1 的正方形
• 正方形邊長為 2
  假如有一個 n 邊常的正方形，且 \(n \geq 2 \) 那他一定會有 \((n-1) * (n-1)\) 個邊長為 2 的正方形。至於為甚麼呢則在下方進行說明
  • 不同的正方形
    因為不同的正方形定義只要裡面其中有一格是與其他正方形不同就可以獨立算是另一個新的正方形，但因為是正方形所以沒有辦法一格不同，只能夠 1 * n。
  • 只需要 1 * n 個不同，我們要極大化正方形數量，因此我們從正方形左上角開始，不斷往下堆疊出邊長為 2 的正方形，會發現只能夠堆疊出 n - 1 個正方形
    • 舉例 n = 3，只能夠堆疊出兩個
      如果想堆疊到第三個會發現會超出邊界，因此不可以
    • 舉例 n = 4，只能夠堆疊出三個
  • 由於正方形長寬都一樣，因此 \( (n-1) * (n-1)\) 就會等於此正方形中邊長為 2 的所有正方形數量
• 正方形邊長為 3
  假如有一個 n 邊常的正方形，且 \(n \geq 3 \) 那他一定會有 \((n-2) * (n-2)\) 個邊長為 3 的正方形。至於為甚麼呢則在下方進行說明
  • 不同的正方形
    因為不同的正方形定義只要裡面其中有一格是與其他正方形不同就可以獨立算是另一個新的正方形，但因為是正方形所以沒有辦法一格不同，只能夠 1 * n。
  • 只需要 1 * n 個不同，我們要極大化正方形數量，因此我們從正方形左上角開始，不斷往下堆疊出邊長為 3 的正方形，會發現只能夠堆疊出 n - 1 個正方形
    • 舉例 n = 3，只能夠堆疊出一個
      如果想堆疊到第二個會發現會超出邊界，因此不可以
    • 舉例 n = 4，只能夠堆疊出兩個
  • 由於正方形長寬都一樣，因此 \( (n-2) * (n-2)\) 就會等於此正方形中邊長為 3 的所有正方形數量
• 下方為圖示，為上方兩個正方形變長的範例

  

• 透過此方式可以推出在正方形邊長為 x 時，那會等於此正方形中邊長為 x 的所有正方形數量公式為 \((n-x) * (n-x) \)，也就是 \(\sum_{i=0}^{n-1} (n-i) * (n-i) \)。

將公式轉換

再來我們將公式進行轉換，\(\sum_{i=0}^{n-1} (n-i) * (n-i) \) 雖然看起來可以用了，但我們還可以把它更優化。

\(\sum_{i=0}^{n-1} (n-i) * (n-i) \) 可以透過平方化簡等於 \(\sum_{i=0}^{n-1} (n-i)^2 \)。

再來，我們舉例假設 n = 3 的時候，應該會是 \((3-0)^2 + (3-1)^2 + (3-2)^2 = 3^2 + 2^2 + 1^2\)，透過這個舉例我們可以再將它化簡為 \(\sum_{i=1}^{n} i^2 \)，而此公式就是大家熟知的連續正整數平方和公式。

連續正整數平方和公式

再來就套用連續平方何公式即可。

關於此公式證明請看圖解連續正整數平方和公式

我會在講解一遍，但我認為我講解的不一定好於是附上網址，讓不懂我講解的人去看此，也謝謝此網站作者將學習資源公布在網路上

證明

• 歸納
  由此圖可知，有 5 個正方形與 5 個長方形組成此圖，且這 5 個正方形邊長分別為 1,2,3,4,5、5 個長方形邊長則為 1 * 1 , 1 * (1+2) , 1 * (1+2+3) , 1 * (1+2+3+4) , 1 * (1+2+3+4+5)。

• 我們想找的面積
  而其實我們想要計算的連續正整數平方和就是紫色面積的正方形總和，如果我們透過數學算式去計算就是總面積減去黃色面積就是我們要查詢的面積。
  於是我們就可以將公式稍微推出來，\([1 + 2 + 3 + … + (n-1) + n ] * (n+1) - [1 + (1+2) + (1+2+3) + … + (1+2+3+4+ … + n )] \)，翻譯成中文就是總面積的長度乘以總面積的高減去黃色部分就是紫色面積。

• 將想找出的面積透過數學方式描述
  \( [1 + (1+2) + (1+2+3) + … + (1+2+3+4+ … + n )] \) 是黃色面積中每一條長方型的面積，總和起來就是總黃色面積。

• 將其公式化
  現在我們可以推出公式 \(\sum_{i=1}^{n} = i^2 = \frac{n(n+1)}{2}(n+1) - \sum_{i = 1}^{n} \frac{i(i+1)}{2} \)，這裡的 \(\frac{i(i+1)}{2} \) 為連續和公式。(梯形公式，上底為 1，下底為 n，高為 n )

• 推導與化簡步驟 1
  再來進行化簡
  \( \frac{n(n+1)}{2}(n+1) - \sum_{i = 1}^{n} \frac{i(i+1)}{2} = \frac{n(n+1)}{2}(n+1) - \frac{1}{2} \sum_{i=1}^{n} i(i+1) \)

• 推導與化簡步驟 2
  \( \frac{n(n+1)}{2}(n+1) - \frac{1}{2} \sum_{i=1}^{n} i(i+1) =\frac{n(n+1)}{2}(n+1) - \frac{1}{2} \sum_{i=1}^{n} i^2 - \frac{1}{2} \sum_{i=1}^{n} i \)，把 \( \sum_{i=1}^{n} i(i+1) \) 拉出來寫

• 推導與化簡步驟 3
  這裡我們要進行移項，還記得一開始是 \(\sum_{i=1}^{n} = i^2 \) 嗎? 是我們不斷進行推導剛剛的步驟。
  \(\sum_{i=1}^{n} = i^2 = \frac{n(n+1)}{2}(n+1) - \frac{1}{2} \sum_{i=1}^{n} i^2 - \frac{1}{2} \sum_{i=1}^{n} i \) 就變成了
  \( \frac{3}{2} \sum_{i=1}^{n} i^2 = \frac{n(n+1)}{2}(n+1) - \frac{1}{2}\sum_{i = 1}^{n} i \)，我們將 \( \frac{1}{2} \sum_{i=1}^{n} i^2 \) 移項至 \(\sum_{i=1}^{n} = i^2\)

• 推導與化簡步驟 4
  \( \frac{n(n+1)}{2}(n+1) - \frac{1}{2}\sum_{i = 1}^{n} i = \frac{n(n+1)}{2}(n+1) - \frac{1}{2} \frac{n(n+1)}{2} \)，將 \(\sum_{i = 1}^{n} i \) 轉換成連續和公式。

• 推導與化簡步驟 5
  \( \frac{n(n+1)}{2}(n+1) - \frac{1}{2} \frac{n(n+1)}{2} = \frac{n(n+1)}{2}(n+1) - (n + 1 - ) \frac{1}{2} \)，\(\frac{1}{2} \frac{n(n+1)}{2}\) 這項進行運算並化簡。

• 推導與化簡步驟 6
  \( \frac{n(n+1)}{2}(n+1) - (n + 1 - ) \frac{1}{2} = \frac{n(n+1)(2n+1)}{4}\)，前面那項進行運算並化簡

• 推導與化簡步驟 7
  還記得剛剛的值是 \( \frac{3}{2} \sum_{i=1}^{n} i^2 \) 嗎？現在我們要在變回 \( \sum_{i=1}^{n} i^2 \)於是
  \( \frac{3}{2} \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{4}\) 將 \( \frac{3}{2} \) 變成移項至另一邊，移項是分數數值會顛倒於是就變成了 \(\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}\)

現在我們有公式了，就來解決吧！，其實寫程式很簡單，如果有推出公式的話XD。

參考來源

• uva：12149－feynman
• 昌爸工作坊
• 微積分老師洪揮霖

心得

老實講，這題我寫的好痛苦XDDD，我自己的數學觀念太差了，雖然看了大神的 blog 得知這題是算出連續正整數平方和公式，但也是花了很多時間才想通QQQQ，再來連續正整數平方和公式我想要推出其證明還卡關…，問了微積分老師洪揮霖(他人很好，幫助我很多數學問題)發現我竟然是卡在移項問題沒看懂..(冏。

因為這題我花的時間比較久且大部分都是在公式推導上於是我就將我的公式推導流程放上來，如果有數學底子跟我一樣差的或許就能看懂了！希望不要有人跟我一樣差拉，很痛苦的，真的。都怪我國中太愛玩都沒有好好上數學課。

總之，學會了，我也變強了，希望之後可以發揮我現在學習的一課！學習 1 小時，寫心得 4 小時是正常的嘛…

題目程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
using namespace std;
int n ;

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAL
    while(cin >> n && n ){
        n = (n * (n+1) * (2*n+1)) / 6 ;
        cout << n << '\n' ;
    }
    return 0;
}

思考流程

透過紙筆與黑板而思考而成的片段，放在網路上供我紀念XD