N^A ≡ N ( mod B )

2 secs 1024 MB
Izayoi_R's icon Izayoi_R

まず結論を述べます。

BB がある11より大きい平方数で割り切れるとき、答えは"No"です
・そうでないとき、BB の全ての素因数 pp について A1A-1p1p-1 で割り切れるならば答えは"Yes"、割り切れない pp があるなら答えは"No"です

以下、証明をしていきます。

BB を割り切るような11より大きい平方数 p2p^2 が存在したとします。 このとき N=BpN=\frac{B}{p} とすると、NAN^ABB の倍数になります。一方で 0<Bp<B0<\frac{B}{p}<B なので NAN^AN(mod B )N(\mod\ B\ ) は成り立ちません。 よってこのとき、答えは"No"です。  

そうでないとき、条件を同値変形して簡単にしていきます。
まず、NNBB の最大公約数を gg とおくと「NAN^AN(mod B )N(\mod\ B\ )」⇔「Ng×NA1\frac{N}{g}\times N^{A-1}Ng(mod Bg )\frac{N}{g}(\mod\ \frac{B}{g}\ )」 ⇔「NA1N^{A-1}1(modBg )1(\mod\frac{B}{g}\ )」となります。
ここで Bg=p1×p2××pm\frac{B}{g} = p_1\times p_2\times\cdots\times p_m と素因数分解します。 すると「NA1N^{A-1}1(modBg )1(\mod\frac{B}{g}\ )」⇔ 「NA1N^{A-1}1(modp1 )1(\mod p_1\ )NA1N^{A-1}1(modp2 )1(\mod p_2\ )\cdotsNA1N^{A-1}1(modpm )1(\mod p_m\ )」と変形出来ます。

次にフェルマーの小定理を用いて変形していきます。 フェルマーの小定理より素数 pp および任意の整数 N,MN,M(ただし ppNN は互いに素)について 「NMN^M1(mod p )1(\mod\ p\ )」⇔「MM0(mod p1 )0(\mod\ p-1\ )」です。これを先ほどの条件に適用すると 「A1A-10(modp11 )0(\mod p_1-1\ )A1A-10(modp21 )0(\mod p_2-1\ )\cdotsA1A-10(modpm1 )0(\mod p_m-1\ )」となります。 この条件は g=1g=1 つまり NNBBが互いに素のときに素因数 pip_i の数が最大となるので最も厳しくなります。逆に、そのときに条件を満たせば十分です。

以上より、最初に述べた結論が得られました。よって BB を素因数分解することで O(B )O(\sqrt{B}\ ) でこの問題を解くことが出来ました。

追記:答えが"No"となる場合、NN が小さい範囲でそのような NN が(少なくとも用意したテストケースには)存在しました。 NN を100まで全探索するだけでもACできちゃいます……。