ArenaRating

solved.ac Grand Arena #2

Solution 1

Implement as given in the problem using a loop. The time complexity is O(N)\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++N=N(N+1)21+2+\cdots+N = \frac{N(N+1)}{2} and 13+23++N3=(1+2++N)2=(N(N+1)2)21^3 + 2^3 + \cdots + N^3 = (1+2+\cdots+N)^2 = {\left(\frac{N(N+1)}{2}\right)}^2 holds. The time complexity is O(1)\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++N=N(N+1)21+2+\cdots+N = \frac{N(N+1)}{2}, let's calculate 2×(1+2++N)2 \times (1 + 2+ \cdots + N).

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

Mathematically:

 2×(1+2++N)= (1+2++N)+(N+(N1)++1)= ((1+N)+(2+(N1))++(N+1))= ((N+1)+(N+1)++(N+1))= N(N+1)\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++N)2=13+23++N3(1+2+\cdots+N)^2 = 1^3+2^3+\cdots+N^3. We will demonstrate that both expressions have the same value for N=1N=1, and the difference between the values of the expressions for N=i1N=i-1 and N=iN=i are the same. This will prove the two expressions are equivalent. For N=1N = 1, both expressions equal 1. Let's now look at the difference between the two expressions:

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

 (1+2++i)2(1+2++(i1)2)= (i(i+1)2)2(i(i1)2)2= (i(i+1)2i(i1)2)×(i(i+1)2+i(i1)2)= (i((i+1)(i1))2)×(i((i+1)+(i1))2)= (i×22)×(i×2i2)= i×i2=i3\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 13+23++(i1)31^3 + 2^3 + \cdots + (i-1)^3 and 13+23++i31^3 + 2^3 + \cdots + i^3 is also i3i^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