この問題は ModularPowerEquation!! の制約を強化したものです。

\(M=1\) の場合は簡単です。以下、 \(2 \le M\) を仮定します。

まず、 \(M\) が奇素数 \(p\) と正整数 \(e\) を用いて \(M=p^e\) と表せる場合を考えます。

また、以下の議論ではまず \(\gcd(A,M)=1\) を仮定します。

\(e=1\) の場合を考えましょう。 \(A^{p(p-1)} \equiv p(p-1) \equiv 0 \pmod p\) ですから、 \(k \bmod {p(p-1)}\) を考えればいいです。ここで、 \(k \bmod {p-1}\) を決め打つことを考えます。この値を \(c\) としましょう。フェルマーの小定理より、条件式は非負整数 \(d \ (0 \le d < p)\) を用いて \(c+d(p-1) \equiv A^c \pmod p\) と言い換えられます。 また、この式は \(d \equiv c-A^c \pmod p\) と言い換えられ、条件を満たす \(d\) は一意に定まります。

\(2 \le e\) について、同様の議論を適用することを考えます。

\(A^c \equiv c \pmod {p^{e-1}}\) を満たす \(c\ (0 \le c < (p-1)p^{e-1})\) が定まっているとしましょう。オイラーの定理より、 \(A^{(p-1)p^{e-1}} \equiv 0 \pmod {p^e}\) ですから、条件式は非負整数 \(d\ (0 \le d < p)\) を用いて \(c + d(p-1)p^{e-1} \equiv A^c \pmod {p^e}\) と書けます。　\(A^c-c \equiv 0 \pmod {p^{e-1}}\) ですから、条件を満たす \(d\) は一意に定まります。

さて、 \(\gcd(A,p)\neq 1\) の場合を考えてみましょう。この場合は \(k \neq 0\) かつ \(k\) が \(p^e\) の倍数であることが必要十分条件です。この証明は簡単だと思います。ここで、 \(\gcd(p-1,p^e)=1\) であることを使うと、 \(\bmod\ p-1\) をどう定めても条件を満たす \(k\ (0 \le k < (p-1)p^e)\) は一意であり、 \(\gcd(A,p)=1\) の時と同様に扱うことができることがわかります。

上の性質を使って \(M\) が一般の場合について解くことを考えます。以下、 \(M\) の素因数分解を \(\prod_{i=1}^s p_i^{e_i}\) とします。普通に garner のアルゴリズムなどをしようとすると、 \(\gcd(p_i-1,p_j-1)\ (i \neq j)\) などが互いに素でない場合があり、構築不能なケースが発生してしまいます。ここで、 \(\bmod\ p-1\) を定めると \(\bmod\ p^e\) が定まることに着目して、 \(p_i\) の昇順に \(k \bmod m\) を定めていくことにしましょう。この時、すべての \(i\) について、 \(\gcd(\mathrm{lcm}(p_1^{e_1},p_1-1,p_2^{e_2},p_2-1,\ldots,p_{i-1}^{e_{i-1}},p_{i-1}-1),p_i) = 1\) が言えます。よって、条件を必ず満たすように解が構築できることが言えました。

計算量は出力数を \(N\) として \(1\) ケース当たり \(O(N\log^2 M + \sqrt M)\) で抑えられます。

実装例 (C++)