指数タワーの値を任意 mod で求める

$2^ {2^ {3}}$ のように指数を連ねた表記を一般に 指数タワー といいます。また、指数タワーが表す値を 指数タワーの値 と呼ぶことにします。ここで、冪乗の演算は右結合、即ち、積みあがった指数の上側から計算することに注意が必要です。例えば、 $2^ {2^ {3}} = 2^ {8} = 256$ となります。
本稿では、次の問題の解法について説明します。

問題正の整数からなる長さ $N$ の数列 $(a_1, a_2, \ldots, a_N)$ 及び正の整数 $M$ が与えられる。
指数タワー $a_1^{a_2^{.^{.^{.^{a_N}}}}}$ の値を $M$ で割った余りを求めよ。

制約

$1 \leq N \leq 10^3$
$1 \leq a_i \leq 10^{1000} \ (1 \leq i \leq N)$
$1 \leq M \leq 10^9$

記法
基本事項
本題
終わりに
参考文献

記法

$\mathbb{N}$ を正の整数全体の集合とします。
$\mathbb{Z}$ を整数全体の集合とします。
非負整数 $x$ 、正の整数 $y$ に対して、 $x \ \mathrm{mod} \ y$ で $x$ を $y$ で割ったときの余りを表します。

基本事項

解説をする際に使用する定理 (定義) をまとめました。
解説で登場した際は、こちらを参照していただければと思います。

定義 $1$ (オイラーのトーシェント関数) $n \in \mathbb{N}$ に対して、 $n$ と互いに素である $1$ 以上 $n$ 以下の整数の個数を $\varphi(n)$ と書き、この関数 $\varphi$ を オイラーのトーシェント関数 と呼ぶ。

定理 $1$ $m, n \in \mathbb{N}$ が互いに素であるならば、

$\varphi(m n) = \varphi(m) \varphi(n)$

が成り立つ。

定理 $2$ $m \in {N}, m \geq 2$ の素因数分解が、

$m = \displaystyle \prod_{i = 1}^{k} p_i^ {e_i}$

と与えられているならば、

$\varphi(m) = \displaystyle \prod_{i = 1}^{k} (p_i - 1) p_i^ {e_i - 1} = m \displaystyle \prod_{i = 1}^{k} \left(1 - \dfrac{1}{p_i} \right)$

が成り立つ。

定理 $3$ (オイラーの定理) $a, n \in \mathbb{N}$ が互いに素であるならば、

$a^ {\varphi(n)} \equiv 1 \pmod n$

が成り立つ。

定理 $4$ (中国剰余定理) $m_1, m_2, \ldots, m_n \in \mathbb{N}$ はどの $2$ つも互いに素であるとする。このとき、 $a_1, a_2, \ldots, a_n \in \mathbb{Z}$ に対して、

$x \equiv a_1 \pmod {m_1},$

$x \equiv a_2 \pmod {m_2},$

$\vdots$

$x \equiv a_n \pmod {m_n}$

を満たす $x \in \mathbb{Z}$ が $m_1 m_2 \cdots m_n$ を法として一意に存在する。

本題

$1 \leq N \leq 10^3$
$1 \leq a_i \leq 10^{1000} \ (1 \leq i \leq N)$
$1 \leq M \leq 10^9$

$a_i = 1$ となる整数 $i \ (1 \leq i \leq N)$ が存在した場合、そのような整数 $i$ のうち最小のものを $i_0$ として $i_0$ 番目以降の項を全て取り去ってしまっても答えは変わりません (任意の $n \in \mathbb{N}$ に対して $1^ n = 1$ であるため)。この操作を行うことによって数列が空となった場合、すなわち $i_0 = 1$ であった場合、答えは明らかに $1 \ \mathrm{mod} \ M$ です。そうでない場合、数列の全ての項が $2$ 以上の整数になります。結果として次の問題に帰着されるので、以下この問題について考えます。

$1 \leq N \leq 10^3$
$\color{red}{2} \leq a_i \leq 10^{1000} \ (1 \leq i \leq N)$
$1 \leq M \leq 10^9$

さて、関数 $f, g$ を以下によって定めます。

$f(i) := \begin{cases} a_i & (i = N) \\ a_i^{f(i + 1)} & (i < N) \end{cases}$

$g(i, m) := f(i) \ \mathrm{mod} \ m$

$(i \in \left\{ 1, 2, \ldots, N \right\}, m \in \mathbb{N})$

求める答えは $g(1, M) = f(1) \ \mathrm{mod} \ M = a_1^ {f(2)} \ \mathrm{mod} \ M$ となります。

関数 $g$ の定め方から、

$g(i, m) = \begin{cases} a_i \ \mathrm{mod} \ m & (i = N) \\ a_i^ {f(i + 1)} \ \mathrm{mod} \ m & (i \lt N) \end{cases}$

と表せます。 $i \lt N$ のとき、そのままでは指数の $f(i + 1)$ が非常に大きくなり得るので、うまく剰余をとるなどして、(答えは変えないまま) 指数の値を小さくしたいです。

ここで一旦、 $m \in \mathbb{N}$ を固定して、任意の $i \in \{ 1, 2, \ldots, N - 1 \}$ に対して $a_i$ と $m$ が互いに素である と仮定してみましょう。

$i \in \{ 1, 2, \ldots, N - 1 \}$ とすると、 $a_i$ と $m$ は互いに素であるため、定理 $3$ (オイラーの定理) により、 $a_i ^ {\varphi(m)} \equiv 1 \pmod m$ が成り立ちます。
ゆえに、 $f(i + 1)$ を $\varphi(m)$ で割ったときの商を $q$ 、余りを $r$ としたとき、

$a_i^ {f(i + 1)} \equiv a_i^ {\varphi(m) q + r} \equiv \left[ a_i^ {\varphi(m)} \right]^ q \cdot a_i^ r \equiv 1^ q \cdot a_i^ r \equiv a_i^ r \pmod m$

が成り立ちます。これより、 $r = f(i + 1) \ \mathrm{mod} \ \varphi(m) = g(i + 1, \varphi(m))$ であることに注意すると、

$g(i, m) = a_i^ {g(i + 1, \varphi(m))} \ \mathrm{mod} \ m$

が成り立つことがわかります。
本問題の制約に合わせて $m \leq 10^ 9$ とすると、指数の $g(i + 1, \varphi(m))$ について、

$g(i + 1, \varphi(m)) = f(i + 1) \ \mathrm{mod} \ \varphi(m) < \varphi(m) \leq m \leq 10^9$

となりますから、無事指数の値を小さくすることに成功しました。

ここまで、任意の $i \in \{ 1, 2, \ldots, N - 1 \}$ に対して $a_i$ と $m$ が互いに素である という仮定の下議論してきましたが、残念ながら今回はそうとは限りません。

しかしながら、以下の補題 $1$ によりほぼ同様の結果が得られます。

補題 $1$ 任意の $a, m, n \in \mathbb{N}, m \geq 2$ に対して、次が成り立つ。

$n \geq \log_2{m} \implies a^ {n + \varphi(m)} \equiv a^ n \pmod m$

証明. $n \geq \log_2{m}$ とし、 $m$ の素因数分解が

$m = \displaystyle \prod_{i = 1}^{k} p_i^ {e_i}$

と与えられているとする。定理 $4$ (中国剰余定理) により、

$\forall i \in \left\{1, 2, \ldots, k\right\}, a^ {n + \varphi(m)} \equiv a^ n \pmod {p_i^ {e_i}} \qquad (\bigstar)$

の成立を言うことができれば、 $a^ {n + \varphi(m)} \equiv a^ n \pmod m$ の成立を言える。
そこで、 $i \in \{1, 2, \ldots, k\}$ を任意とする。

$\mathrm{(i)}$ $a$ が $p_i$ を素因数に持たない場合

$a$ と $p_i^ {e_i}$ は互いに素であるから、定理 $3$ (オイラーの定理) により、 $a^ {\varphi\left(p_i^ {e_i}\right)} \equiv 1 \pmod {p_i^ {e_i}}$ が成り立つ。定理 $2$ により、 $\varphi\left(p_i^ {e_i}\right)$ は $\varphi(m)$ の約数であるから、 $a^ {\varphi(m)} \equiv 1 \pmod {p_i^ {e_i}}$ となり、 $a^ {n + \varphi(m)} \equiv a^ n \pmod {p_i^ {e_i}}$ が成り立つ。

$\mathrm{(ii)}$ $a$ が $p_i$ を素因数に持つ場合

$a = {p_i^ {e'}} {a'} \ ({e'}, {a'} \in \mathbb{N})$ と表せる。もし、 $n \geq e_i$ ならば、

$a^ n \equiv \left({p_i^ {e'}} {a'} \right)^ n \equiv {\left(p_i^ n\right)^ {e'}} {a'}^ n \equiv 0 \pmod {p_i^ {e_i}}$

が成り立つ。これより、

$n \geq e_i \implies a^ {n + \varphi(m)} \equiv {a^ n} \cdot {a^ {\varphi(m)}} \equiv 0 \equiv a^ n \pmod {p_i^ {e_i}} \qquad (\spadesuit)$

が成り立つ。
さて、 $2^ {e_i} \leq p_i^ {e_i} \leq m$ であるから、 $e_i \leq \log_2 m$ である。仮定と合わせて、 $n \geq e_i$ であるから、 $(\spadesuit)$ により、 $a^ {n + \varphi(m)} \equiv a^ n \pmod {p_i^ {e_i}}$ が成り立つ。

$\mathrm{(i), (ii)}$ により、 $(\bigstar)$ の成立が言えたので、 $a^ {n + \varphi(m)} \equiv a^ n \pmod m$ が成立する。 $\Box$

補題 $1$ により、 $i \lt N, m \geq 2$ のとき、以下が成立します。*1

$f(i + 1) \geq \log_2 m$ ならば、 $g(i, m) = a_i^ {f(i + 1) \ \mathrm{mod} \ \varphi(m) + \varphi(m)} \ \mathrm{mod} \ m = a_i^ {g(i + 1, \varphi(m)) + \varphi(m)} \ \mathrm{mod} \ m$
$f(i + 1) \lt \log_2 m$ ならば、 $g(i, m) = a_i^ {f(i + 1)} \ \mathrm{mod} \ m$

本問題では $m \leq 10^ 9$ の場合を考えれば良いので、 $f(i + 1) \lt \log_2 m \lt 30$ の場合は、関数 $g$ の定義に従って、愚直に求められるということに注意してください。

$f(i + 1)$ と $\log_2 m$ の大小を比較する必要がありますが、以下のいずれかに該当する場合は $f(i + 1) \lt 30$ となり、そうでない場合は $f(i + 1) \geq \log_2 m$ が成り立ちます。

$i = N - 1$ かつ $a_{i + 1} \lt 30$
$i = N - 2$ かつ

$\begin{aligned} (a_{i + 1}, a_{i + 2}) = &(2, 2), (2, 3), (2, 4), \\ &(3, 2), (3, 3), \\ &(4, 2), \\ &(5, 2) \end{aligned}$

$i = N - 3$ かつ $(a_{i + 1}, a_{i + 2}, a_{i + 3}) = (2, 2, 2)$

以上をまとめると、関数 $g$ の擬似コードは以下のようになります。なお、

pow(a, b, m) は $a^ b \ \mathrm{mod} \ m$
pow(a, b) は $a^ b$
totient(m) は $\varphi(m)$
a[i] は $a_i$
a % m は $a \ \mathrm{mod} \ m$

をそれぞれ表すものとします。

また、任意の非負整数 $a, b$ 、正の整数 $m$ に対して、

$a^ b \ \mathrm{mod} \ m = (a \ \mathrm{mod} \ m)^ b \ \mathrm{mod} \ m$

が成り立つこと、さらに、任意の $i \in \{1, 2, \ldots, N \}$ に対して

$g(i, 1) = a_i^ {f(i + 1)} \ \mathrm{mod} \ 1 = 0$

が成り立つことに注意してください。

function g(i, m) {
    if (m == 1) return 0;
    if (i == N) return a[i] % m;
    if (i == N - 1 && a[i + 1] < 30) {
        return pow(a[i] % m, a[i + 1], m);
    }
    if (i == N - 2) {
        if ((a[i + 1] <= 5 && a[i + 2] == 2) ||
            (a[i + 1] == 2 && a[i + 2] <= 4) ||
            (a[i + 1] == 3 && a[i + 2] == 3)) {
            return pow(a[i] % m, pow(a[i + 1], a[i + 2]), m);
        }
    }
    if (i == N - 3) {
        if (a[i + 1] == 2 && a[i + 2] == 2 && a[i + 3] == 2) {
            return pow(a[i] % m, 8, m);
        }
    }
    return pow(a[i] % m, g(i + 1, totient(m)) + totient(m), m);
}

最後に時間計算量を見積もってみましょう。
まずは、時間計算量を見積もる上で重要となる次の補題を示します。

補題 $2$ 任意の $m \in \mathbb{N}, m \geq 2$ に対して、次が成り立つ。

$\varphi \left( \varphi(m) \right) \leq m/2$

証明. $m \in \mathbb{N}, m \geq 2$ とし、 $m$ の素因数分解が、

$m = \displaystyle \prod_{i = 1}^{k} p_i^ {e_i}$

と与えられているとする。このとき、定理 $2$ により、

$\begin{aligned} \varphi(m) &= \displaystyle \prod_{i = 1}^{k} (p_i - 1) p_i^ {e_i - 1} \\ &= m \displaystyle \prod_{i = 1}^{k} \left(1 - \dfrac{1}{p_i} \right) \end{aligned}$

が成り立つ。
$1$ つ目の形から、 $m$ が奇数ならば $\varphi(m)$ は偶数となることがわかり、
$2$ つ目の形から、 $m$ が偶数ならば $\varphi(m) \leq m/2$ となることがわかる。
また、任意の $n \in \mathbb{N}$ に対して、 $\varphi(m) \leq m$ が成り立つ。
以上により、 $m$ が奇数ならば、

$\varphi \left( \varphi(m) \right) \leq \varphi(m)/2 \leq m/2$

が従い、 $m$ が偶数ならば、

$\varphi \left( \varphi(m) \right) \leq \varphi(m) \leq m/2$

が従う。よって、 $\varphi \left( \varphi(m) \right) \leq m/2$ が成り立つ。 $\Box$

先ほどの擬似コードでは、関数 $g$ を呼び出すたびに第 $2$ 引数に $\varphi$ を適用しているため、補題 $2$ により第 $2$ 引数の値は急激に小さくなり、やがて $m = 1$ となります。よって、高々 $2 \times \log_2{M} \lt 60$ 回の再帰で停止させることができます。

function g(i, m) {
    if (m == 1) return 0;
    if (i == N) return a[i] % m;
    if (i == N - 1 && a[i + 1] < 30) {
        return pow(a[i] % m, a[i + 1], m);
    }
    if (i == N - 2) {
        if ((a[i + 1] <= 5 && a[i + 2] == 2) ||
            (a[i + 1] == 2 && a[i + 2] <= 4) ||
            (a[i + 1] == 3 && a[i + 2] == 3)) {
            return pow(a[i] % m, pow(a[i + 1], a[i + 2]), m);
        }
    }
    if (i == N - 3) {
        if (a[i + 1] == 2 && a[i + 2] == 2 && a[i + 3] == 2) {
            return pow(a[i] % m, 8, m);
        }
    }
    return pow(a[i] % m, g(i + 1, totient(m)) + totient(m), m);
}

以上を踏まえて、 $\varphi(m)$ の計算に $O(\sqrt m)$ かけるとすると、 $\varphi$ の計算には全体で、