C++로 B!/A! 나눗셈 결과의 마지막 자릿수 구하기

두 정수 A와 B가 주어지고 B ≥ A일 때, B!/A! 연산 결과의 마지막 자릿수를 구하는 문제를 살펴보겠습니다.

예를 들어 A = 2, B = 4인 경우를 생각해 봅시다. 2! = 2이고 4! = 24이므로, 24 ÷ 2 = 12가 됩니다. 따라서 마지막 자릿수는 2입니다.

해결 아이디어

팩토리얼 값의 마지막 자릿수는 항상 {0, 1, 2, 4, 6} 중 하나라는 성질을 이용하면 다음과 같은 단계로 문제를 효율적으로 해결할 수 있습니다.

• A와 B의 차이(diff)를 구합니다.
• 차이가 5 이상이면, 그 범위 안에 반드시 5의 배수가 포함되므로 마지막 자릿수는 0입니다.
• 그렇지 않다면 (A + 1)부터 B까지 숫자를 하나씩 곱하면서 매번 10으로 나눈 나머지만 저장합니다.
• 최종 곱셈 결과의 마지막 자릿수가 곧 정답입니다.

예제 코드

#include<iostream>
using namespace std;
int findLastDigit(long long int A, long long int B) {
    int x = 1;
    if (A == B)
        return 1;
    else if ((B - A) >= 5)
        return 0;
    else {
        for (long long int i = A + 1; i <= B; i++)
            x = (x * (i % 10)) % 10;
        return x % 10;
    }
}
int main() {
    cout << "Last digit is: " << findLastDigit(2, 4);
}

실행 결과

Last digit is: 2

코드 설명

위 코드는 먼저 A와 B가 같은 경우를 확인합니다. 이때 B!/A! = 1이므로 마지막 자릿수는 1을 반환합니다. 다음으로 B − A가 5 이상인지 검사하여, 참이라면 곱셈 과정에서 일의 자리가 0이 되므로 즉시 0을 반환해 불필요한 연산을 줄입니다. 그 외의 경우에는 (A + 1)부터 B까지 각 숫자의 일의 자리만 곱하고 10으로 나눈 나머지를 유지함으로써, 큰 수의 오버플로우 없이 마지막 자릿수만 정확히 계산할 수 있습니다.