solved.ac Grand Arena #2

Solution 1

Implement as given in the problem using a loop. The time complexity is $\mathcal O(N)$ .

Code (C++)

#include <iostream>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int sum_1 = 0, sum_3 = 0;
    for (int i = 1; i <= N; i++)
    {
        sum_1 += i;
        sum_3 += i * i * i;
    }
    cout << sum_1 << endl;
    cout << sum_1 * sum_1 << endl;
    cout << sum_3 << endl;
}

Code (Python)

def main():
    N = int(input())
    print(sum(range(1, N+1)))
    print(sum(range(1, N+1))**2)
    print(sum(i**3 for i in range(1, N+1)))


if __name__ == '__main__':
    main()

Solution 2

$1+2+\cdots+N = \frac{N(N+1)}{2}$ and $1^3 + 2^3 + \cdots + N^3 = (1+2+\cdots+N)^2 = {\left(\frac{N(N+1)}{2}\right)}^2$ holds. The time complexity is $\mathcal O (1)$ .

Code (C++)

#include <iostream>
using namespace std;

int main()
{
    int N;
    cin >> N;
    cout << N * (N + 1) / 2 << endl;
    cout << (N * (N + 1) / 2) * (N * (N + 1) / 2) << endl;
    cout << (N * (N + 1) / 2) * (N * (N + 1) / 2) << endl;
}

Code (Python)

def main():
    N = int(input())
    print(N * (N + 1) // 2)
    print((N * (N + 1) // 2) ** 2)
    print((N * (N + 1) // 2) ** 2)


if __name__ == '__main__':
    main()

증명

To prove $1+2+\cdots+N = \frac{N(N+1)}{2}$ , let's calculate $2 \times (1 + 2+ \cdots + N)$ .

When adding two sequences of $(1+2+\cdots+N)$ , keep one sequence as it is, and reverse the other before adding. Then, upon inspecting each sum, combining $1$ with $N$ yields $N+1$ , combining $2$ with $N−1$ yields $N+1$ , and so on, until combining $N$ with $1$ also gives $N+1$ . Hence, the total is equivalent to adding $N+1$ a total of $N$ times, which is $N(N+1)$ .

Mathematically:

\begin{align*} & \ 2 \times (1 + 2 + \cdots + N) \\ = & \ (1 + 2 + \cdots + N) + (N + (N-1) + \cdots + 1) \\ = & \ ((1+N) + (2+(N-1)) + \cdots + (N+1)) \\ = & \ ((N+1) + (N+1) + \cdots+ (N+1)) \\ = & \ N(N+1) \end{align*}

$Visual proof for 1+2+\cdots+N = \frac{N(N+1)}{2}$

Let's now prove the slightly more challenging relationship $(1+2+\cdots+N)^2 = 1^3+2^3+\cdots+N^3$ . We will demonstrate that both expressions have the same value for $N=1$ , and the difference between the values of the expressions for $N=i-1$ and $N=i$ are the same. This will prove the two expressions are equivalent. For $N = 1$ , both expressions equal 1. Let's now look at the difference between the two expressions:

Utilizing the identity $a^2 - b^2 = (a-b)(a+b)$ :

\begin{align*} & \ (1+2+\cdots+i)^2 - (1+2+\cdots+(i-1)^2) \\ = & \ \left(\frac{i(i+1)}{2}\right)^2 - \left(\frac{i(i-1)}{2}\right)^2 \\ = & \ \left(\frac{i(i+1)}{2} - \frac{i(i-1)}{2}\right) \times \left(\frac{i(i+1)}{2} + \frac{i(i-1)}{2}\right) \\ = & \ \left(\frac{i((i+1)-(i-1))}{2}\right) \times \left(\frac{i((i+1)+(i-1))}{2}\right) \\ = & \ \left(\frac{i \times 2}{2} \right) \times \left(\frac{i \times 2i}{2} \right) \\ = & \ i \times i^2 = i^3 \end{align*}

The difference between $1^3 + 2^3 + \cdots + (i-1)^3$ and $1^3 + 2^3 + \cdots + i^3$ is also $i^3$ , so the two expressions must indeed be equivalent.

There's also a visual method to prove this.

$Visual proof for (1+2+\cdots+N)^2 = 1^3+2^3+\cdots+N^3$