양의 정수 num과 x가 주어졌을 때, numx를 계산한 뒤 그 결과값의 각 자릿수를 반복해서 더해 한 자리 숫자가 될 때까지 처리하고, 마지막으로 남은 한 자리 숫자를 출력하는 것이 이 글의 목표입니다.
n과 x가 매우 크다면 num^x 값을 직접 계산하는 것 자체가 불가능합니다. 따라서 실제 거듭제곱을 구하지 않고도 답을 구할 수 있는 수학적 성질, 즉 디지털 루트(Digital Root) 개념을 활용해야 합니다.
입력 · 출력 예시
예시 1
입력 − int num = 2345, int x = 3
출력 − 매우 큰 n과 x에 대한 n^x의 자릿수 재귀 합: 8
설명 − num = 2345, 지수 = 3입니다. 먼저 2345³ = 12,895,213,625를 계산하고, 각 자릿수를 더하면 1 + 2 + 8 + 9 + 5 + 2 + 1 + 3 + 6 + 2 + 5 = 44가 됩니다. 다시 4 + 4 = 8이므로 한 자리 숫자에 도달했으며, 따라서 출력은 8입니다.
예시 2
입력 − int num = 3, int x = 3
출력 − 매우 큰 n과 x에 대한 n^x의 자릿수 재귀 합: 9
설명 − num = 3, 지수 = 3입니다. 3³ = 9이며 이미 한 자리 숫자이므로 추가 계산 없이 출력은 9입니다.
핵심 원리: 디지털 루트와 모듈로 9
자릿수를 반복해서 더해 얻는 한 자리 숫자는 원래 수를 9로 나눈 나머지와 같다는 성질이 있습니다(단, 9의 배수인 경우에는 9). 예를 들어 12,895,213,625를 9로 나눈 나머지는 8로, 위 예시 1의 결과와 정확히 일치합니다.
또한 어떤 수를 9로 나눈 나머지의 거듭제곱은 최대 주기 6으로 순환하므로, 지수를 6으로 나눈 나머지(temp = power % 6)만 확인하면 충분합니다. 이 두 가지 성질 덕분에 아주 큰 수라도 실제 거듭제곱을 계산하지 않고 빠르게 답을 구할 수 있습니다.
알고리즘 접근 방식
- 정수 변수 num과 x를 입력받아 함수 Recursive_Digit(num, x)에 전달합니다.
- 함수 Recursive_Digit(num, x) 내부에서:
- long형 변수 total을 선언하고, 인자로 전달된 수의 자릿수 합(디지털 루트)을 반환하는 total_digits(num)의 호출 결과로 초기화합니다.
- long형 변수 temp를 선언하고 power % 6 값으로 설정합니다.
- total이 3 또는 6이면서 power가 1보다 크면 9를 반환합니다.
- 그렇지 않고 power가 1이면 total을 반환합니다.
- power가 0이면 1을 반환합니다.
- temp가 0이면 total_digits((long)pow(total, 6))의 결과를 반환합니다.
- 그 외의 경우에는 total_digits((long)pow(total, temp))의 결과를 반환합니다.
- 함수 long total_digits(long num) 내부에서:
- num이 0이면 0을 반환하고, num % 9가 0이면 9를 반환합니다.
- 그렇지 않으면 num % 9를 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 한 자리 숫자가 될 때까지 자릿수 합을 구하는 함수 (디지털 루트)
long total_digits(long num){
if(num == 0){
return 0;
}
if(num % 9 == 0){
return 9;
}
else{
return num % 9;
}
}
// n^x의 자릿수 재귀 합을 구하는 함수
long Recursive_Digit(long num, long power){
long total = total_digits(num);
long temp = power % 6;
if((total == 3 || total == 6) && power > 1){
return 9;
}
else if(power == 1){
return total;
}
else if(power == 0){
return 1;
}
else if(temp == 0){
return total_digits((long)pow(total, 6));
}
else{
return total_digits((long)pow(total, temp));
}
}
int main(){
int num = 2345;
int x = 98754;
cout << "매우 큰 n과 x에 대한 n^x의 자릿수 재귀 합: " << Recursive_Digit(num, x);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
매우 큰 n과 x에 대한 n^x의 자릿수 재귀 합: 1
마무리
이처럼 디지털 루트와 모듈로 9의 성질을 활용하면, 일반적인 자료형으로는 표현조차 어려운 거대한 n^x 값의 자릿수 합도 상수 시간에 가까운 속도로 구할 수 있습니다. 특히 지수가 수천, 수만 단위로 매우 큰 경우에도 동일하게 적용할 수 있다는 점이 이 기법의 가장 큰 장점입니다.