ZeroJudge 解題筆記：e417.乘法~乘法~加法~

作者：王一哲
日期：2026年9月13日


ZeroJudge 題目連結：e417.乘法~乘法~加法~

解題想法

題目是多筆測資。每組測資有 $2$ 列，第 $1$ 列給一個整數 $n$，第 $2$ 列給 $n$ 個整數 $x_1, x_2, x_3, \dots, x_n$，題目要求 $x_1 x_2 + x_1 x_3 + x_1 x_4 \dots + x_{n-2} x_n + x_{n-1} x_n$，保設答案可以用 unsigned long long 格式儲存。這一題如果用迴圈硬算會超時，需要利用一個數學性質，假設要計算的數字為 $a, b, c, d$，則 $$ \begin{align*} (a + b + c + d)^2 &= a^2 + ab + ac + ad + b^2 + ba + bc + bd +\\ &+ c^2 + ca + cb + cd + d^2 + da + db + dc\\ &= a^2 + b^2 + c^2 + d^2 + 2(ab + ac + ad + bc + bd + cd)\\ \end{align*} $$ $$ ab + ac + ad + bc + bd + cd = \frac{(a + b + c + d)^2 - (a^2 + b^2 + c^2 + d^2)}{2} $$ 雖然題目給的記憶體很大，但是用 Python 解題時，不能用 sys.stdin.read().split() 一次讀取並分割所有的測資，這樣會超出記憶體上限。要改用生成器，一次轉換一個數字。

Python 程式碼

使用時間約為 32 ms，記憶體約為 69.6 MB，通過測試。

def solve():
    import sys
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield int(part)

    tokens = get_tokens()

    while True:
        try:
            n = next(tokens)
        except StopIteration:
            break
        
        square = 0  # 平方項的和
        total = 0  # 數字加總
        for _ in range(n):
            x = next(tokens)
            square += x*x
            total += x
        ans = (total * total - square) // 2
        sys.stdout.write(f"{ans:d}\n")

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 0.5 s，記憶體約為 3.5 MB，通過測試。

#include <iostream>
typedef unsigned long long LL;
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    LL n;
    while(cin >> n) {
        LL square = 0, total = 0;
        for(LL i = 0; i < n; i++) {
            LL x; cin >> x;
            square += x * x;
            total += x;
        }
        LL ans = (total * total - square) / 2;
        cout << ans << "\n";
    }
    return 0;
}

使用時間約為 0.7 s，記憶體約為 1.6 MB，通過測試。

#include <cstdio>
typedef unsigned long long LL;

int main() {
    LL n;
    while(scanf("%llu", &n) != EOF) {
        LL square = 0, total = 0;
        for(LL i = 0; i < n; i++) {
            LL x; scanf("%llu", &x);
            square += x * x;
            total += x;
        }
        LL ans = (total * total - square) / 2;
        printf("%llu\n", ans);
    }
    return 0;
}

C 語言程式碼

使用時間約為 0.7 s，記憶體約為 1.5 MB，通過測試。

#include <stdio.h>
typedef unsigned long long LL;

int main() {
    LL n;
    while(scanf("%llu", &n) != EOF) {
        LL square = 0, total = 0;
        for(LL i = 0; i < n; i++) {
            LL x; scanf("%llu", &x);
            square += x * x;
            total += x;
        }
        LL ans = (total * total - square) / 2;
        printf("%llu\n", ans);
    }
    return 0;
}