$M - K = 1$ というコーナーケースにやられた！

問題へのリンク

問題概要

整数 $N, M, K$ が与えられる。

$2^{N}$ を $2^{M} - 2^{K}$ で割った余りの一の位の値を求めよ。

(マルチテストケース)

制約

$1 \le N \le 10^{18}$
$1 \le K \lt M \le 10^{18}$

考えたこと

まず最初に考えたのは「全体を $2^{K}$ で割った世界」で考えれば良いということ。

このことを正当化しよう。一般に、次のことが成り立つ。

整数 $a, b, k$ と正の整数 $m$ に対して

$a \equiv b \pmod m$

であることと、

$ka \equiv kb \pmod{km}$

であることは同値である。

つまり、 $2^{N-K}$ を $2^{M-K} - 1$ で割った余りを $r$ とすると、

$2^{N-K} \equiv r \pmod{2^{M-K} - 1}$

と表せるが、これを全体に $2^{K}$ 倍して得られる

$2^{N} \equiv 2^{K}r \pmod{2^{M} - 2^{K}}$

は同値だということだ。

よって、この問題の答えは

$2^{N-K}$ を $2^{M-K} - 1$ で割った余りを求めて、 $2^{K}$ をかけた値

となることがわかった。

例外処理

ただし、 $N \lt K$ の場合は例外なので例外扱いする。

この場合は、 $2^{N} \lt 2^{K} \le 2^{M} - 2^{K}$ であるから、答えは $2^{N}$ である。

本題

以降、 $N \ge K$ とする。そして、「 $2^{N-K}$ を $2^{M-K} - 1$ で割った余り」を頑張って求める。

ここで、今度は次のことに注目しよう。

相異なる整数 a, b と、整数多項式 $f(x)$ に対して、次のことが成り立つ。

$f(a) \equiv f(b) \pmod{a - b}$

つまり、 $\pmod{a - b}$ についての合同式を考えるとき、 $a$ の部分をそのまま $b$ に置き換えてよいということだ！！！

そうすると、たとえば $N - K = 14, M - K = 3$ のとき、次のように式変形できる。

$2^{14} = (2^{3})^{4} \times 2^{2} \equiv 1^{4} \times 2^{2} = 2^{2} \pmod{2^{3} - 1}$

より一般に、 $N - K$ を $M - K$ で割った余りを $r$ とすると、次のようになる。

$2^{N - K} \equiv 2^{r} \pmod{2^{M-K} - 1}$

よって、この問題の答えは $2^{r+K}$ である。あとは、この値を 10 で割った余りを求めれば OK。

計算量は $O(\log N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

template<class T> T mod_pow(T a, T n, T m) {
    T res = 1;
    while (n > 0) {
        if (n % 2 == 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
};

void solve() {
    long long N, M, K;
    cin >> N >> M >> K;
    
    if (N < K) {
        cout << mod_pow(2LL, N, 10LL) << endl;
    } else {
        if (M - K == 1)
            cout << 0 << endl;
        else
            cout << mod_pow(2LL, (N - K) % (M - K) + K, 10LL) << endl;
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
}