【Uva 解題筆記】12149 - Feynman

Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3301

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=a111

PDF Source：https://onlinejudge.org/external/121/12149.pdf

題目翻譯：

理查·菲利普斯·費曼（Richard Phillips Feynman）是一位著名的美國物理學家，也是諾貝爾物理學獎得主。他從事理論物理學研究，同時也開創了量子計算領域。他曾到南美洲待了十個月，在熱帶地區演講並享受生活。他也以他的著作「別鬧了，費曼先生！」和「你管別人怎麼想？」而聞名，這些書中包含了一些他在赤道以下的冒險經歷。

他一生都熱衷於解謎題、製作鎖和密碼。最近，一位曾在 1949 年接待這位年輕物理學家的南美洲老農夫，找到了一些被認為是費曼所留下的文件和筆記。在關於介子和電磁學的筆記中，有一張餐巾紙上寫著一個簡單的謎題：「在 N × N 的方格中有多少個不同的正方形？」

在同一張餐巾紙上有一張圖示（如下方所示），顯示當 N = 2 時，答案是 5。

Input

輸入包含數個測資。每組測資由單獨一行組成，只包含一個整數 N，代表方格每邊的正方形數量（1 ≤ N ≤ 100）。

Output

輸入包含數個測資。每個測資由單獨一行組成，只包含一個整數 N，代表方格每邊的正方形數量（1 ≤ N ≤ 100）。

Sample Input

2
1
8
0

Sample Output

5
1
204

解題思路：

這題其實蠻簡單的，稍微觀察一下就會發現有所端倪：

• $N = 1, 1^2 = 1$
• $N = 2, 1^2 + 2^2 = 5$
• $N = 3, 1^2 + 2^2 + 3^2 = 14$
• $N = 4, 1^2 + 2^2 + 3^2 + 4^2 = 30$

最後就會得到這樣的式子： $1^2 + 2^2 + 3^2 + 4^2 + \cdots + N^2$

那這東西有一個公式，相信各位高中數學都學得非常透徹，都知道這是 $\frac{N(N+1)(2N+1)}{6}$ 吧。

範例程式碼：

#include <iostream>

using namespace std;

int main(){
    int N;
    ios::sync_with_stdio(false), cin.tie(nullptr);
    while (cin >> N && N != 0){
        int result = (N*(N + 1)*(2*N + 1)) / 6;
        cout << result << "\n";
    }
    return 0;
}