Problem 6 : Sum square difference (5%)

Description

The sum of the squares of the first ten natural numbers is,

\[1^2 + 2^2 + ... + 10^2 = 385\]

The square of the sum of the first ten natural numbers is,

\[(1 + 2 + ... + 10)^2 = 552 = 3025\]

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

1부터 100까지 자연수의 합의 제곱과 제곱의 합의 차이를 구하시오.

반복문으로 구현해서 풀면된다. 이렇게 풀어도 연산 $O(n)$이고 long long 범위이기에 괜찮다.

하지만 n이 커진다면 다음과 같이 제곱의 합과 합의 제곱을 다음과 같은 식으로 표현할 수 있다.

\[\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}\] \[(\sum_{i=1}^n i)^2 = (\frac{n(n+1)}{2})^2\]

이를 이용해서 $O(1)$으로 구할 수도 있다.

#include <stdio.h>

int main(){
    int n = 100;
    printf("%d", (n*n*(n+1)*(n+1))/4-(n*(n+1)*(2*n+1))/6);
}