1834 - 나머지와 몫이 같은 수

N = 1 일 때
N = 2 일 때
N = 3 일 때

자연수 1 부터 적당한 수까지 직접 해보면 규칙이 보인다.

규칙을 찾기 힘들다면 아래를 참고해보자.

•  나머지(R)는 나누는 수(N)보다 클 수 없다.

그럼 이렇게 생각해 볼 수 있다.

• N으로 나누었을 때 나올 수 있는 나머지의 종류는 0, ... N-1 이다.

이 말을 다시 해석하면

• R = [0, ... N-1] 인 수열에 대해, A_k = k * R_k + R_k (k ≥ 0) 인 수열의 합이다.
  (R_k은 몫이지만 나머지와 같고, Ak 는 원래의 숫자를 도출한 것이다.)

수열 A에 있는 원소들의 합이 곧 정답이다. 수열 A부터 살펴보면,
A_k = k * R_k + R_k = k * (R_k + 1) 로 나타낼 수 있고
이 수열은 A₀ = 0, A₁ = 1 * 2, A₂ = 2 * 3 ... 이런식이다.

점화식으로 풀어내자면,
A₀ + A₁ + ... + A_n-1> + A_n = ( 0 * 1 ) + ( 1 * 2 ) + ... ( (n-1) * n ) + ( n * (n+1) )
  = (n-1) * n * (n+1) / 2     ∵ 합 공식
  = (n² - 1) * n / 2        ∵ 합차공식


PS. 나머지와 몫을 묶어서 설명했는데, 몫이 0 일 경우는 없을 것이므로, A₀ 은 무시해도 된다.
PS. 몫은 quotient, 나머지는 remainder.