Xmas Contest 2018 J: Japanese Exponentation 解説

https://atcoder.jp/contests/xmascon18/tasks/xmascon18_j

問題概要

四の三の二乗乗 みたいなのを $\operatorname{mod} (10^9 + 9)$ で計算せよ．

解法

UTF-8 の文字列を処理する方法は，皆さんお使いのプログラミング言語ごとに調べてください．

冪乗を $\operatorname{mod} m$ で計算する方法を考えます．「 $a_1 \equiv a_2 \pmod{m}$ のとき $a_1^b \equiv a_2^b \pmod{m}$ 」は正しいですが，「 $b_1 \equiv b_2 \pmod{m}$ のとき $a^{b_1} \equiv a^{b_2} \pmod{m}$ 」は正しくないので，指数は勝手に $\operatorname{mod} m$ をとってはいけません．

とはいえ， $\operatorname{mod} m$ での $a^0, a^1, a^2, \ldots$ は必ずどこかから周期的になります．最初から周期に入っているとは限りません．例えば $m = 12,\, a = 2$ のときは $1, 2, 4, 8, 4, 8, \ldots$ となり， $a^2$ から長さ $2$ の周期に入ります．どこからどんな長さの周期に入るかについては，以下の事実がよく知られており (補足参照)，この問題ではこれで十分です：

$b \ge \log_2 m$ なら， $a^b, a^{b+1}, \ldots$ は既に周期に入っている．
周期の長さは $\varphi(m)$ の約数である．ただし $\varphi$ は Euler の φ 関数．

というわけで，指数はおおよそは $\operatorname{mod} \varphi(m)$ でもっておけばいいですが，小さい値，雑に $32$ 未満くらいは特別に扱う必要があります．実装上は，例えば次のいずれかのような方針がわかりやすいと思います：

$\operatorname{mod} m$ をとる代わりに， $32$ 以上の整数は $32, \ldots, 32 + m - 1$ に収めるようにする ( $x \, (\ge 32)$ を $32 + ((x - 32) \bmod m)$ にする)．
整数 $x$ の計算結果として， $(x \bmod m, \min\{x, 32\}$ ) の組をもつ．

以上をふまえると，構文解析パート (再帰下降) を合わせて解答は次のようになります．

Result expr(m):  // Result 型は上記のように特殊な mod のとり方をした整数
  Result a := number(m)  // 整数を読む
  while 次の文字が "の":
    "の" を読む
    Result b := expr(φ(m))
    a := a^b  // 繰り返し二乗法などで計算
    "乗" を読む
  return a

なお， $10^9+9, \varphi(10^9+9), \varphi(\varphi(10^9+9)), \ldots$ は $25$ 回で $1$ になるので，同じ $\varphi$ の計算を複数回しないようにすれば実行時間は大丈夫です．

補足

$\operatorname{mod} m$ での $a^0, a^1, a^2, \ldots$ の様子について，もうちょっとちゃんとした話をします．

中国剰余定理より， $m$ としては素冪 $p^e$ だけ考えればよいです．素冪ごとに考えた後で，周期に入る場所は $\max$ をとればいいし，周期の長さ (の倍数) は最小公倍数をとればいいです．

$a = p^k a_0$ ( $k$ は非負整数， $a_0$ は $p$ で割れない) と書くと， $k \ge 1$ のとき $p^k$ の部分は累乗していくと途中からずっと $0$ になってしまい，これが周期の前の部分を作っている要因です．高々 $e$ 乗で $0$ になるので，周期に入るまでの長さは $e$ 以下です．一方 $a_0$ の部分だけ見ると最初から周期に入っていて，その周期は