n번째 항이 n² − (n−1)²인 급수의 합을 구하는 C/C++ 프로그램

수학에는 C 프로그래밍으로 손쉽게 풀 수 있는 다양한 종류의 급수가 있습니다. 이번 포스팅에서는 다음과 같은 급수의 합을 구하는 방법을 살펴보겠습니다.

Tn = n2 - (n-1)2

급수의 모든 항의 합 S_n을 다음 조건에 맞게 구합니다.

S_n = T₁ + T₂ + T₃ + T₄ + ...... + T_n

입력: 229137999
출력: 218194447

풀이 설명

T_n은 간단한 전개를 통해 2n-1 형태로 표현할 수 있습니다.

식을 전개해 보면,

=> Tn = n² - (n-1)²
=> Tn = n² - (1 + n² - 2n)
=> Tn = n² - 1 - n² + 2n
=> Tn = 2n - 1

이제 ∑T_n을 구해 보겠습니다.

∑Tn = ∑(2n – 1)
위 식을 정리하면,
=> ∑(2n – 1) = 2*∑n – ∑1
=> ∑(2n – 1) = 2*∑n – n

여기서 ∑n은 처음 n개의 자연수의 합을 의미합니다.

n개 자연수의 합 공식은 잘 알려져 있듯이 ∑n = n(n+1)/2 입니다.

이를 식에 대입하면,

∑Tn = (2*(n)*(n+1)/2) - n = n²

n² 값은 n이 커지면 매우 큰 수가 될 수 있습니다. 따라서 결과에 직접 mod 연산을 취하는 대신, 모듈러 곱셈의 성질을 활용하여 n²을 계산하는 것이 효율적입니다.

(a*b)%k = ((a%k)*(b%k))%k

예제 코드

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