問題リンク
atcoder.jp
問題概要
正整数 $ A, M $ が与えられるので、
$$
A ^ x \equiv x \pmod M
$$
を満たす $2\times 10 ^ {18}$ 以下の正整数 $x$ を一つ求めよ。
制約
$1\leq A\leq 10 ^ 9$
$1\leq M\leq 10 ^ 9$
解法
Step 1.
$\gcd(A,M)=1$ ならば $ A ^ { \phi (M) } \equiv 1 \pmod M $ なので、まずはこの場合に帰着したい。
まず、$1\leq x\leq \lfloor \log _ 2 M\rfloor$ の場合を愚直に試し、答えが見つかれば直ちに出力して終了する。
以下、$x\gt\lfloor\log _ 2 M\rfloor$ とする。
このとき、$g\coloneqq\gcd(A ^ {\text{(十分大きな整数)}}, M)$ に対して答えとなる $x$ は $\gcd(A ^ {x},M)=g$ を満たす。従って、$g\mid A ^ x$ および $ g \mid M $ が成り立つから、
$$
\begin{aligned}
& A ^ x \equiv x \pmod M \\
\Rightarrow & \exists k \in \mathbb{Z} \; \text{ s.t. } \; A ^ x - x = k M \\
\Rightarrow & \exists k \in \mathbb{Z} \; \text{ s.t. } \; \frac{x}{g} = \frac{A ^ x}{g} - k \cdot \frac{M}{g} \in \mathbb{Z} \\
\Rightarrow & g \mid x
\end{aligned}
$$
が必要である。$x=gx'$ を満たす正整数 $x'$ および $ M = g M' $ をみたす正整数 $M'$ を導入し、満たすべき条件式を
$$
\begin{cases}
g x ' \gt \lfloor \log _ 2 M \rfloor \\
A ^ {g x '} \equiv g x ' \pmod {M '}
\end{cases}
$$
と書き換える。ここで、一つ目の条件が必要なことに注意する。ただし、求めた答えが小さすぎた場合は条件を満たすようになるまで周期を足すだけでよいので、以降はこの条件を考えない。
さて、この時点で $\gcd(A,M')=1$ となり、扱いやすくなった。加えて、$\gcd(g,M')=1$ も成立していることに注意する。
Step 2.
$ B \coloneqq A ^ g $ とすれば、条件式は
$$ B ^ {x '} \equiv g x ' \pmod{M '} $$
と書ける。$\gcd(A,M')=1$ なので $\gcd(B,M')=1$ であり、つまり左辺の周期は $\phi(M')$ の約数となる。そこで、$x'=q\cdot \phi(M')+r$ を満たす整数 $q,r$ を導入すると
$$ B ^ r \equiv g \cdot ( q \cdot \phi ( M ' ) + r ) \pmod { M ' } $$
となる。$r=0$ としてみると、
$$1\equiv g\cdot q\cdot \phi(M')\pmod{M'}$$
となる。いま $\gcd(g,M')=1$ なので、$\bmod M'$ において $g$ の乗法逆元は必ず存在する。一方、$\phi(M')$ に関しては $\gcd(M',\phi(M'))=1$ とは限らないが、仮にこれが成り立つとすれば、
$$q\equiv\bigl(g\cdot\phi(M')\bigr)^{-1}\pmod{M'}$$
を満たす $q$ を選ぶことで条件を満たす $x'$ を求めることが出来る (先述の通り、この時点で答えが小さすぎた場合は適切に数周期分だけ足す必要がある)。
残ったのは、$\gcd(M',\phi(M'))\neq 1$ の場合である。
Step 3.
条件式を $q,r$ で分離して
$$ g ^ { - 1 } \cdot B ^ r - r \equiv q \cdot \phi ( M ' ) $$
とする。見やすさのため、左辺を一時的に $a(r)$ と表記する。つまり、
$$a(r)\equiv q\cdot \phi(M')\pmod {M'}$$
である。$g'\coloneqq \gcd(M',\phi(M'))\gt 1$ とおけば、上式より
$$
\begin{aligned}
& a(r) \equiv q \cdot \phi ( M ' ) \pmod { M ' } \\
\Rightarrow & \exists k \in \mathbb{Z} \; \text{ s.t. } \; a(r) - q \cdot \phi ( M ' ) = k M ' \\
\Rightarrow & \exists k \in \mathbb{Z} \; \text{ s.t. } \; \frac{ a ( r ) }{ g ' } = q \cdot \frac { \phi ( M ' ) }{ g ' }+k \cdot \frac{ M ' } { g ' } \in \mathbb{Z} \\
\Rightarrow& g ' \mid a(r)
\end{aligned}
$$
が必要である。$\gcd\left(\dfrac{\phi(M')}{g'},\dfrac{M'}{g'}\right)=1$ であるから、$g'\mid a(r)$ を満たす $r$ が一つ求まれば、$q$ は
$$q\equiv\frac{a(r)}{g'}\cdot\left(\frac{\phi(M')}{g'}\right)^{-1}\pmod{\frac{M'}{g'}}$$
を満たすものを選べばよく、この問題が解けたことになる。ここで、$g'\mid a(r)$ を満たす $r$ はどのようなものであるかを考えると
$$
\begin{aligned}
& g'\mid a(r)\\
\Leftrightarrow & a(r)\equiv 0 \pmod{g'}\\
\Leftrightarrow & g ^ {-1}\cdot B ^ r\equiv r\pmod{g'}
\end{aligned}
$$
となり、元の問題と非常によく似た構造が現れる。少し異なるのは左辺に係数が付いている点であるが、この係数を加えても今までと全く同様の議論が行えるため、初めから係数付きの問題を解いており、元の問題はその係数が $1$ であるような特殊ケースだと思えば自然な再帰 構造となる。
再帰 的に問題を解けばよいことが分かったので、終端条件を確認する。$g'\lt\phi(M')\lt M'$ および $ g' \mid M' \mid M $ から、法 $ M $ が必ず $ M $ 以外の約数へと移っていくことが分かる。従って、最終的には $1$ となるか、あるいは途中で Step 1 や Step 2 で確認したような部分的に解けるケースに帰着されることで終端する。従って $M=1$ のケースだけ処理すれば良く、このケースは容易に解くことが出来る。
以上より、TL に間に合うかと値の上限制約を考えなければ、この問題を解くことが出来た。
上限制約
合同式 の周期は $\mathrm{lcm}(\phi(M),M)\leq 10^{18}$ の約数なので、計算途中に適切に mod を取ればこの制約を破らないような解が構成できる。
計算量解析
まず、Step 1 で $1\leq x\leq\lfloor \log_2 M\rfloor$ を試すパートは愚直にやっても $O(\log M\log \log M)$ である。Step 2 や Step 3 では定数回の $\gcd$ およびモジュラ逆数の計算を行うが、これらは $O(\log M)$ である。Step 2, 3 で $\phi(M')$ が必要となるが、これは $N$ の素因数分解 表示
$$N=\prod_{p}p^{q_p}$$
に対して
$$\phi(N)=\prod_{p} p^{q_p}\left(1-\dfrac{1}{p}\right)$$
として求められることを利用すれば $O(\sqrt{M})$ で求めることが出来る。以上より、再帰 の 1 段分の計算量は $O(\sqrt{M})$ である。
再帰 の段数は、$ M $ が毎回半分以下になるので $O(\log M)$ で押さえることができる。
$$ \sum _ {i=0} ^ {\infty}\frac{1}{2 ^ i}+\frac{1}{2 ^ i\sqrt{2}}=2+\sqrt{2}\lt\infty$$
より、全体でも $O(\sqrt{M})$ であり、十分高速である。
所感
銀 diff なので当然難しいし、解説はかなり天才的でびっくりした。ただどこかで同じような議論を見たことがある気がしていて、不動点 典型 (？) だったりするのかな。
自分の解法と公式解説で共通してるのはある程度 $ x $ が大きいことを課せば再帰 できるってことで、これは離散対数問題を任意 mod で解く時にも使うから他の問題でも使うことがあるかもしれないと思ったり。
