ZeroJudge 解題筆記：a111. 12149 - Feynman

作者：王一哲
日期：2025年12月16日


ZeroJudge 題目連結：a111. 12149 - Feynman

解題想法

如果 $n = 1$ 答案為 $1$；如果 $n = 2$，答案為 $1 + 4 = 1 + 2^2 = 5$；如果 $n = 3$，答案有邊長 3 的正方形 1 個，邊長 2 的正方形 4 個，邊長 1 的正方形 9 個，也就是 $1 + 4 + 9 = 1 + 2^2 + 3^2 = 14$。解題時可以建表或是代公式 $$ ans = \sum_{i = 1}^n i^2 = \frac{n(n+1)(2n+1)}{6} $$

Python 程式碼

建表，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

dp = [0]*101
dp[0] = 0
dp[1] = 1
for i in range(2, 101):
    dp[i] = dp[i-1] + i*i

for line in sys.stdin:
    n = int(line)
    if n == 0: continue
    print(dp[n])

代公式，使用時間約為 20 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)
    if n == 0: continue
    print(n*(n+1)*(2*n + 1)//6)

C++ 程式碼

建表，使用時間約為 2 ms，記憶體約為 328 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int dp[101] = {0};
    dp[0] = 0; dp[1] = 1;
    for(int i=2; i<=100; i++) dp[i] = dp[i-1] + i*i;
    int n;
    while(cin >> n) {
        if (n == 0) continue;
        cout << dp[n] << "\n";
    }
    return 0;
}

建表，使用時間約為 2 ms，記憶體約為 56 kB，通過測試。

#include <cstdio>

int main() {
    int dp[101] = {0};
    dp[0] = 0; dp[1] = 1;
    for(int i=2; i<=100; i++) dp[i] = dp[i-1] + i*i;
    int n;
    while(scanf("%d", &n) != EOF) {
        if (n == 0) continue;
        printf("%d\n", dp[n]);
    }
    return 0;
}

代公式，使用時間約為 2 ms，記憶體約為 284 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    int n;
    while(cin >> n) {
        if (n == 0) continue;
        cout << n*(n+1)*(2*n + 1)/6 << "\n";
    }
    return 0;
}

代公式，使用時間約為 2 ms，記憶體約為 88 kB，通過測試。

#include <cstdio>

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        if (n == 0) continue;
        printf("%d\n", n*(n+1)*(2*n + 1)/6);
    }
    return 0;
}