Xmas Contest 2018 J: Japanese Exponentation 解説
https://atcoder.jp/contests/xmascon18/tasks/xmascon18_j
問題概要
四の三の二乗乗
みたいなのを で計算せよ.
解法
UTF-8 の文字列を処理する方法は,皆さんお使いのプログラミング言語ごとに調べてください.
冪乗を で計算する方法を考えます.「
のとき
」は正しいですが,「
のとき
」は正しくないので,指数は勝手に
をとってはいけません.
とはいえ, での
は必ずどこかから周期的になります.最初から周期に入っているとは限りません.例えば
のときは
となり,
から長さ
の周期に入ります.どこからどんな長さの周期に入るかについては,以下の事実がよく知られており (補足参照),この問題ではこれで十分です:
なら,
は既に周期に入っている.
- 周期の長さは
の約数である.ただし
は Euler の φ 関数.
というわけで,指数はおおよそは でもっておけばいいですが,小さい値,雑に
未満くらいは特別に扱う必要があります.実装上は,例えば次のいずれかのような方針がわかりやすいと思います:
をとる代わりに,
以上の整数は
に収めるようにする (
を
にする).
- 整数
の計算結果として,
) の組をもつ.
以上をふまえると,構文解析パート (再帰下降) を合わせて解答は次のようになります.
Result expr(m): // Result 型は上記のように特殊な mod のとり方をした整数 Result a := number(m) // 整数を読む while 次の文字が "の": "の" を読む Result b := expr(φ(m)) a := a^b // 繰り返し二乗法などで計算 "乗" を読む return a
なお, は
回で
になるので,同じ
の計算を複数回しないようにすれば実行時間は大丈夫です.
補足
での
の様子について,もうちょっとちゃんとした話をします.
中国剰余定理より, としては素冪
だけ考えればよいです.素冪ごとに考えた後で,周期に入る場所は
をとればいいし,周期の長さ (の倍数) は最小公倍数をとればいいです.
(
は非負整数,
は
で割れない) と書くと,
のとき
の部分は累乗していくと途中からずっと
になってしまい,これが周期の前の部分を作っている要因です.高々
乗で
になるので,周期に入るまでの長さは
以下です.一方
の部分だけ見ると最初から周期に入っていて,その周期は
かつ
のとき
- その他のとき
の約数です.さらに,実際にこれらの周期をとる が存在します (原始根の存在定理など).
ここまで考察すると,この問題で必要な は
だけで済むことがわかります.
コメント
この問題は,本当に問題文のストーリー通りの流れで作りました.「 の
乗」の構文は,
になっていて面白いです.
マルチバイト文字は,こういうコンテストだからこその出題という感じですね.いろいろ調べていたら 六
にだけ互換文字があるとかいう知識が増えてしまいました.
数学パートは,「普段なんとなくで をとっていませんか?」というメッセージ (?) です.