C++에서 주어진 n에 대한 (n¹ + n² + n³ + n⁴) mod 5 값 구하기

문제 소개

이 문제에서는 정수 n이 하나 주어지며, 주어진 n에 대해 (n¹ + n² + n³ + n⁴) mod 5의 값을 구하는 것이 목표입니다.

예시를 통해 문제를 살펴보겠습니다.

입력 : n = 5
출력 : 0

풀이 설명 −

(5¹ + 5² + 5³ + 5⁴) mod 5
= (5 + 25 + 125 + 625) mod 5
= 780 mod 5 = 0

방법 1: 식을 직접 계산하기

가장 단순한 접근 방식은 주어진 n에 대해 네 항을 모두 더한 값을 그대로 계산한 뒤, 그 결과를 5로 나눈 나머지를 반환하는 것입니다. 다만 n이 커지면 n⁴ 값이 int 자료형의 표현 범위를 쉽게 초과할 수 있으므로, 오버플로를 방지하려면 long long 타입을 사용하는 것이 안전합니다.

예제 코드

#include <iostream>
using namespace std;

int findMod5Val(int n){
   long long val = (long long)n + (long long)n*n + (long long)n*n*n + (long long)n*n*n*n;
   return val % 5;
}

int main(){
   int n = 12;
   cout << "N = " << n << "일 때, (n^1 + n^2 + n^3 + n^4) % 5의 값은 " << findMod5Val(n);
   return 0;
}

실행 결과

N = 12일 때, (n^1 + n^2 + n^3 + n^4) % 5의 값은 0

방법 2: 수학적 공식으로 최적화하기

식을 인수분해하면 훨씬 효율적인 풀이를 도출할 수 있습니다. 함수 f(n)을 다음과 같이 변형해 보겠습니다.

f(n) = n + n² + n³ + n⁴
f(n) = n × (1 + n + n² + n³)
f(n) = n × {(1 + n) + n² × (1 + n)}
f(n) = n × (1 + n) × (1 + n²)
f(n) = n × (n + 1) × (n² + 1)

이렇게 인수분해된 형태를 분석해 보면, n을 5로 나눈 나머지 값에 따라 f(n) mod 5의 결과는 0 또는 4 중 하나로 결정됩니다.

n % 5 == 1인 경우: 네 항이 모두 5로 나누면 나머지 1이 되므로, 합의 나머지는 1 + 1 + 1 + 1 = 4입니다.
그 외의 경우(n % 5가 0, 2, 3, 4): 네 항의 합이 항상 5의 배수가 되므로 결과는 0입니다.

n % 5 == 1이면,
   f(n) % 5 = 4
그 외의 경우,
   f(n) % 5 = 0

이 규칙을 활용하면 거듭제곱 계산 없이 O(1) 시간 복잡도로 답을 구할 수 있습니다.

예제 코드

#include <iostream>
using namespace std;

int findMod5Val(int n){
   if(n % 5 == 1)
      return 4;
   return 0;
}

int main(){
   int n = 66;
   cout << "N = " << n << "일 때, (n^1 + n^2 + n^3 + n^4) % 5의 값은 " << findMod5Val(n);
   return 0;
}

실행 결과

N = 66일 때, (n^1 + n^2 + n^3 + n^4) % 5의 값은 4

마무리

직접 계산하는 방법은 이해하기 쉽지만 n이 커질수록 오버플로와 성능 문제가 발생할 수 있습니다. 반면 인수분해를 통해 도출한 규칙을 사용하면 어떤 크기의 n이 들어와도 단 한 번의 나머지 연산만으로 정답을 구할 수 있으므로, 실무적으로는 두 번째 방법이 훨씬 유리합니다.