C#で Project Euler P6

問題

Problem 6 「二乗和の差」
最初の10個の自然数について, その二乗の和は,
12 + 22 + ... + 102 = 385
最初の10個の自然数について, その和の二乗は,
(1 + 2 + ... + 10)2 = 3025
これらの数の差は 3025 - 385 = 2640 となる.
同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ.
Problem 6 - PukiWiki

解答

using System;

public static class P6
{
    public static void Main()
    {
        Console.WriteLine(Calc());
    }
    
    private static long Calc()
    {
        long res = 0;
        long sum = 0;
        for(int a = 100 - 1; a >= 1; a--)
        {
            sum += a + 1;
            res += sum * a;
        }
        return res * 2;
    }
}

計算量　$O(n)$

二乗の和を式１、和の二乗を式２とすると、 \begin{align*} 式２=&(N_1 + N_2 + N_3 + ... + N_n)^2 \\ = &N_1N_1+N_1N_2+N_1N_3+...+N_1N_n+N_2N_1+N_2N_2+N_2N_3+...+N_2N_n+ \\ &N_3N_1+N_3N_2+N_3N_3+...+N_3N_n+...+N_nN_1+N_nN_2+N_nN_3+...+N_nN_n \\ = &(N_1^2+N_2^2+N_3^2+...+N_n^2)+2\{N_1(N_2+N_3+...+N_n)+N_2(N_3+...+N_n)+...N_{n-1}(N_n)\}\\ =&Σ_{k=1}^n N_k^2 + 2Σ_{k=1}^{n-1}N_kΣ_{j=k+1}^{n}j \end{align*} ここで、 \begin{align*} 式１ = &Σ_{k=1}^n N_k^2 \end{align*} であるため、 \begin{align*} 式２-式１ = &Σ_{k=1}^n N_k^2 + 2Σ_{k=1}^{n-1}N_kΣ_{j=k+1}^{n}N_j - Σ_{k=1}^n N_k^2\\ =&2Σ_{k=1}^{n-1}N_kΣ_{j=k+1}^{n}N_j \end{align*} と表せる。
この形で実装しやすいように、$2Σ_{k=1}^{n-1}N_kΣ_{j=k+1}^{n}N_j$を降順にした。