C++でB!÷A!の最後の桁を求めるアルゴリズム

問題の概要

2つの整数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）を求める
• diff ≥ 5 の場合、答えは 0 になる
• diff < 5 の場合は、(A + 1) から B までの各数値を順に掛け合わせる
• 掛け合わせた結果の最後の桁が答えとなる

diff ≥ 5 のときに答えが 0 になる理由は、連続する5つ以上の整数の中には必ず5の倍数と偶数が含まれ、それらを掛け合わせると10の倍数になるためです。

C++での実装例

#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が等しい場合は商が1になるため1を返し、差が5以上の場合は0を返します。それ以外の場合は、(A + 1) から B までの各数値の下一桁だけを掛け合わせ、10で剰余を取ることで最後の桁を求めています。階乗全体を計算しないため、大きな数値でもオーバーフローを気にせず高速に処理できるのが特徴です。