部分点解法

Fermat の小定理より、\(x \equiv N \pmod M\) かつ \(x \equiv 1 \pmod {M - 1}\) を満たす \(x\) について \(x^x \equiv N^1 \equiv N \pmod M\) となります。

\(\gcd (M, M - 1) = 1\) よりこのような \(x\) は常に存在し、具体的に \(x = M^2 - MN + N\) ととれます。

満点解法

\(x = 1, 2, \ldots, 30\) について愚直に全探索を行い、以下は \(x \geq 31\) なる解についてのみ考えます。

\(M = \prod p_i ^ {e_i}\) と素因数分解を行い、\(p_i < p_{i + 1}\) とします。\(x \geq 31\) より、\(p_i \mid x \iff p_i^{e_i} \mid x^x\) に注意してください。

\(i\) の昇順（すなわち \(p_i\) の昇順に）\(x \equiv x' \pmod m\) という形の条件を与えていきます。ただし、\(x \equiv 0 \pmod m\) という条件はできる限り与えないように工夫して条件を与えていきます（\(N\) の素因数でない素数 \(p\) については \(x \equiv 0 \pmod p\) という条件が与えられず、\(N\) の素因数 \(p\) についても \(x \equiv 0 \pmod {p^2}\) という条件が与えられないようにします）。

\(p_i ^ {e_i} \mid N\) のときは単に \(x \equiv 0 \pmod {p_i}\) という条件を与えます。

\(p_i \mid N\) だが \(p_i ^ {e_i} \mid N\) でないときは条件を満たす \(x\) は存在しません。

以下 \(p_i\) が \(N\) を割り切らないとします。

\(\text{mod }p_i\) における原始根 \(r\) を取り、\(r ^ s \equiv N \pmod {p_i}\) なる \(s\) を取ります。また、\(u \coloneqq \gcd(s, p_i - 1)\) とします。このとき \(\text{mod }p_i\) における \(N\) の位数は \(\frac{p_i - 1}{u}\) です。\(p_i - 1\) の約数 \(v\) であって \(u\) を割り切らないものについて \(\text{mod }v\) で \(0\) という条件が与えられているとき、\(x^x\) の \(\text{mod } p_i\) での位数は \(\frac{p_i - 1}{v}\) の約数となるため条件を満たす整数 \(x\) が存在しないことが確定します。以下そのような状況でないことを仮定します。(\(\bigstar\))

これまでの条件により \(x \equiv t \pmod {p_i - 1}\) というように指定されているような \(t\) を取ります。\(\text{mod }p_i - 1\) での値が指定されていないこともありますが、そのときは \(\text{mod }hoge\) で \(0\) という条件を新たに与えないように適切に \(\text{mod } p_i - 1\) での値を指定します。

このようなことが常に可能であることの証明

$p_i - 1$ の約数であって $\text{mod } m_0$ での値が指定されているような最大の $m_0$ を取る。$p_i - 1 = \prod q_j ^ {f_j}$ とおく。$q_j$ が $m_0$ の素因数でないときは $\text{mod } q_j ^ {f_j}$ で $1$ というように適当に定めればよい。$q_j$ が $m_0$ の素因数であるときは、$q_j$ が $m_0$ を割り切る回数を $o$ として、$o < f_j$ かつ $\text{mod } q_j ^ o$ で $0$ という条件が与えられているときは $\text{mod } q_j ^ {f_j}$ で $q_j^o$、そうでないときは $\text{mod } q_j ^ o$ で $y$ という条件が与えられているとして $\text{mod } q_j ^ {f_j}$ で $y$ という条件を与えればよい。

このとき、\(a\) についての方程式 \(at \equiv s \pmod {p_i - 1}\) について考えます。

(\(\bigstar\)) の条件からこの方程式は常に解を持ちます。したがって、解 \(a\) を取り、\(x \equiv t \pmod {p_i - 1}\) に加えて \(x \equiv r^a \pmod {p_i}\) という条件を与えると、\(x^x \equiv (r^a)^t \equiv r^{at} \equiv r^s \equiv N \pmod {p_i}\) となることがわかります。\(p_i\) の昇順に処理していることから、これ以前に \(\text{mod } p_i\) での条件が与えられていることはないことに注意してください。

これで \(\text{mod } p_i\) の条件は満たされたので、\(\text{mod } p_i ^ {e_i}\) での条件を満たすために順に持ち上げていきます。

\(\text{mod } p_i ^ k\) の条件が満たされているとして、\(\text{mod }p_i ^ {k + 1}\) の条件を満たすように条件を指定します。

\(q \coloneqq (p_i - 1)p_i ^ k\) とおきます。\(\text{mod } q\) で \(w\) という形の条件が与えられているとします。このとき、整数 \(j\) について \((w + jq) ^ {w + jq} \equiv (w + jq)^w \equiv w^w(1 + jq) \pmod {p_i ^ {k + 1}}\) であるため（\(1\) つ目の等号は Euler の定理、\(2\) つ目の等号は二項定理から従います）、 適切な \(j\) を選ぶことで \(\text{mod } p_iq\) で \(w + jq\) という形の条件を与えればよいことがわかります。ここでも \(p_i\) の昇順に処理していることから、これ以前に \(\text{mod } p_i^{k + 1}\) での条件が与えられていることはないことに注意してください。

以上により解が存在しないか、\(x \equiv x' \pmod m\) なる \(x\) が解となるかの結論を得ることができました。\(m \leq M(M - 1)\) であるため解が存在するならば \(x \leq 10^{18}\) であるようなものが取れます。また、\(x\) が十分大きい必要があることに注意してください（例えば \(x' = 2\) のときは \(x = 2\) ではなく \(x = m + 2\) と取る必要がある場合があります）。

実装方法によりますが、時間計算量は素因数分解や離散対数の計算がボトルネックとなって \(O(\sqrt M)\) などになります。

Bonus : （\(x\) の範囲を \(10^{36}\) まで許容して）\(M \leq 10^{18}\) で解けます。

略解

素因数分解は高速素因数分解を用いればよいです。 離散対数（$s$ を得るパート）は実際に $s$ を計算する必要はなく、$N$ の $\text{mod }p_i$ における $t$ 乗根を計算すればよいので一般冪乗根（yukicoder No.981）を用いればできます。