まず結論を述べます。
・B がある1より大きい平方数で割り切れるとき、答えは"No"
です
・そうでないとき、B の全ての素因数 p について A−1 が p−1 で割り切れるならば答えは"Yes"
、割り切れない p があるなら答えは"No"
です
以下、証明をしていきます。
B を割り切るような1より大きい平方数 p2 が存在したとします。
このとき N=pB とすると、NA は B の倍数になります。一方で 0<pB<B なので NA ≡ N(mod B ) は成り立ちません。
よってこのとき、答えは"No"
です。
そうでないとき、条件を同値変形して簡単にしていきます。
まず、N と B の最大公約数を g とおくと「NA ≡ N(mod B )」⇔「gN×NA−1 ≡ gN(mod gB )」
⇔「NA−1 ≡ 1(modgB )」となります。
ここで gB=p1×p2×⋯×pm と素因数分解します。
すると「NA−1 ≡ 1(modgB )」⇔
「NA−1 ≡ 1(modp1 ) ∧ NA−1 ≡ 1(modp2 ) ∧ ⋯ ∧ NA−1 ≡ 1(modpm )」と変形出来ます。
次にフェルマーの小定理を用いて変形していきます。
フェルマーの小定理より素数 p および任意の整数 N,M(ただし p と N は互いに素)について
「NM ≡ 1(mod p )」⇔「M ≡ 0(mod p−1 )」です。これを先ほどの条件に適用すると
「A−1 ≡ 0(modp1−1 ) ∧ A−1 ≡ 0(modp2−1 ) ∧ ⋯ ∧ A−1 ≡ 0(modpm−1 )」となります。
この条件は g=1 つまり N と Bが互いに素のときに素因数 pi の数が最大となるので最も厳しくなります。逆に、そのときに条件を満たせば十分です。
以上より、最初に述べた結論が得られました。よって B を素因数分解することで O(B ) でこの問題を解くことが出来ました。
追記:答えが"No"
となる場合、N が小さい範囲でそのような N が(少なくとも用意したテストケースには)存在しました。
N を100まで全探索するだけでもACできちゃいます……。