[C++] 주어진 5자리 숫자를 5제곱한 값의 마지막 5자리 구하기

문제 개요

이 문제에서는 하나의 숫자 N이 주어집니다. 우리가 해야 할 작업은 주어진 5자리 숫자를 5제곱한 값의 마지막 다섯 자리를 구하는 것입니다.

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

입력: N = 25211

출력: 5제곱한 값의 마지막 다섯 자리

풀이 접근 방법

이 문제를 해결하려면 결과값 전체가 아니라 마지막 다섯 자리만 구하면 됩니다. 곱셈 연산에서 마지막 자릿수는 피연산자들의 마지막 자릿수에만 의존하기 때문에, 모듈로(나머지) 연산을 활용하면 효율적인 해결이 가능합니다.

구체적인 접근 방법은 다음과 같습니다. 거듭제곱을 한 단계씩 수행할 때마다 그 결과를 100000으로 나눈 나머지를 취하여 항상 뒤 5자리만 유지합니다. 이렇게 하면 중간 계산값이 아무리 커져도 오버플로우 없이 처리할 수 있으며, 5제곱 연산이 모두 끝난 후 남은 마지막 5자리를 최종 결과로 반환하면 됩니다.

솔루션 동작 예시 프로그램

예제 코드

#include <iostream>
using namespace std;

int lastFiveDigits(int n) {
    int result = 1;
    for (int i = 0; i < 5; i++) {
        result *= n;
        result %= 100000;
    }
    cout<<"The last five digits of "<<n<<" raised to the power 5 are "<<result;
}

int main() {
    int n = 12345;
    lastFiveDigits(n);
    return 0;
}

출력 결과

The last five digits of 12345 raised to the power 5 are 65625

실행 결과를 보면, 12345를 5제곱한 값의 마지막 다섯 자리는 65625임을 확인할 수 있습니다. 반복문 내부에서 매 단계마다 100000으로 나머지 연산을 수행하기 때문에, 실제로 엄청나게 큰 5제곱 값을 직접 계산하지 않고도 필요한 자릿수만 빠르고 정확하게 얻을 수 있습니다.