C/C++ 프로그램 – n번째 항이 n² − (n−1)²인 수열의 합 구하기

이 글에서는 n번째 항이 n² − (n−1)²로 주어지는 수열의 합을 구하는 방법을 알아보겠습니다. 이 수열의 일반항은 다음과 같습니다.

T_n = n² − (n−1)²

수열의 패턴 분석

일반항을 전개하면 다음과 같이 간단히 단순화할 수 있습니다.

T_n = n² − (n² − 2n + 1) = 2n − 1

즉, 이 수열은 1, 3, 5, 7, … 과 같은 홀수 수열입니다. 처음 n개의 홀수의 합은 잘 알려진 공식에 따라 다음과 같습니다.

S = 1 + 3 + 5 + … + (2n − 1) = n²

따라서 반복문 없이도 수열의 합을 한 번의 연산으로 바로 구할 수 있습니다. 문제에서는 수열의 모든 항의 합 S를 (10⁹ + 7)로 나눈 나머지를 구해야 하므로, 값이 커지는 것을 방지하기 위해 모듈로 연산을 적용합니다.

예제 코드

#include<iostream>
#define X 1000000007
using namespace std;
long long getSum(long long n) {
   return ((n % X) * (n % X)) % X;
}
int main() {
   long long n = 56789;
   cout << getSum(n);
}

출력 결과

224990500

코드 설명

getSum 함수는 입력값 n을 먼저 X(10⁹ + 7)로 나눈 나머지를 구한 뒤 제곱하고, 그 결과를 다시 한 번 X로 나눈 나머지를 반환합니다. 중간 결과마다 모듈로 연산을 적용하면 long long 범위 안에서 오버플로우 없이 안전하게 계산할 수 있습니다.

예를 들어 n = 56789인 경우, 수열의 합은 56789² = 3,224,990,521이고, 이를 1,000,000,007로 나눈 나머지는 224,990,500이 됩니다.