이 문제에서는 두 개의 수 a와 b가 주어지며, 우리의 목표는 매우 큰 수에 대해서도 a^b의 마지막 자릿수를 구하는 것입니다.
예시를 통해 문제를 살펴보겠습니다.
입력: a = 4, b = 124
출력: 6
설명:
4124의 실제 값은 약 4.523128486 × 1074로, 일반적인 정수 자료형으로는 전혀 담을 수 없는 어마어마한 크기입니다. 하지만 우리에게 필요한 것은 전체 값이 아니라 마지막 한 자릿수뿐입니다.
해결 접근 방법
이 문제의 핵심은 거듭제곱의 마지막 자릿수는 지수가 4를 주기로 반복된다는 수학적 성질에 있습니다.
예를 들어 밑이 2인 경우 마지막 자릿수는 2 → 4 → 8 → 6 순으로 반복되고, 밑이 3인 경우에는 3 → 9 → 7 → 1 순으로 반복됩니다. 즉, 어떤 수든 거듭제곱의 마지막 자릿수 패턴은 최대 4개입니다.
또한 거듭제곱의 마지막 자릿수는 밑(base)의 마지막 자릿수에 의해서만 결정됩니다. 따라서 결과값은 다음과 같이 계산할 수 있습니다.
(a의 마지막 자릿수) ^ (b % 4)
여기서 주의할 점은 b % 4가 0일 때 지수를 4로 처리해야 한다는 것입니다. 나머지가 0이라는 것은 지수가 4의 배수, 즉 주기의 마지막 단계에 해당하기 때문입니다.
구현 시 고려해야 할 특수 경우
- a와 b가 모두 "0"인 경우: 관례상 00은 1로 처리합니다.
- 지수 b가 0인 경우: 어떤 수의 0제곱은 항상 1입니다.
- 밑 a가 0인 경우: 결과는 항상 0입니다.
또한 a와 b가 매우 클 수 있으므로 문자열 형태로 입력받고, b % 4는 각 자릿수를 순회하며 모듈로 연산을 적용해 계산합니다.
솔루션 동작을 보여주는 프로그램
#include <bits/stdc++.h>
using namespace std;
// 문자열로 표현된 큰 수 b를 a로 나눈 나머지를 계산
int calcModulus(char b[], int a)
{
int mod = 0;
for (int i = 0; i < strlen(b); i++)
mod = (mod * 10 + b[i] - '0') % a;
return mod;
}
int calcLastDigitInExpo(char a[], char b[]) {
int len_a = strlen(a), len_b = strlen(b);
// 둘 다 0인 경우: 0^0 = 1로 처리
if (len_a == 1 && len_b == 1 && b[0] == '0' && a[0] == '0')
return 1;
// 지수가 0인 경우: 결과는 항상 1
if (len_b == 1 && b[0] == '0')
return 1;
// 밑이 0인 경우: 결과는 항상 0
if (len_a == 1 && a[0] == '0')
return 0;
// 지수 주기 계산: b % 4가 0이면 4 사용
int exponent = (calcModulus(b, 4) == 0) ? 4 : calcModulus(b, 4);
int base = a[len_a - 1] - '0';
int result = pow(base, exponent);
return result % 10;
}
int main()
{
char a[] = "559", b[] = "4532";
cout<<"The last digit in of the value is "<<calcLastDigitInExpo(a, b);
return 0;
}출력
The last digit in of the value is 1
코드 설명
calcModulus 함수는 문자열로 표현된 거대한 지수 b를 4로 나눈 나머지를 구합니다. 각 자릿수를 왼쪽부터 순회하며 (mod * 10 + 현재 자릿수) % 4를 반복 적용하면, 오버플로우 없이 나머지를 얻을 수 있습니다.
calcLastDigitInExpo 함수는 먼저 위에서 언급한 세 가지 특수 경우를 처리한 뒤, 밑의 마지막 자릿수와 주기가 적용된 지수를 이용해 최종 결과를 계산합니다.
이 방식의 시간 복잡도는 문자열 길이에 비례하는 O(len(b))로, 지수가 아무리 커도 매우 빠르게 마지막 자릿수를 구할 수 있다는 것이 가장 큰 장점입니다.