Baby-step giant-stepによる解法とWeb公式解説の理解メモ
公式解説の理解
を
で割って良い理由
とします。
を変形し、
とします。
は
の倍数となる必要があります。
の倍数であるとは、約数として
を含むということです。
ここで、
となるので、
が
の倍数なら、
を約数に含むこととなり、
は
の倍数となります。
したがって、元の問題を
という問題に帰着させることができます。
の時に解なしになる理由
という問題は、
を満たす整数を求める問題とみなせます。この問題に解が存在するための必要十分条件は、
・が
で割り切れること
です。しかし、単にこの条件を見るだけでは、が必ずしも1である必要はありません。
では、なぜ解を持つ時に必ずが成り立つことかを考えてみます。
とします。
(1) のとき
すなわちが
を約数に持つ場合です。
この時、は共通の約数が無くなって、
となります。
この時、当然を割り切ることができ、解を持ちます。
(2) のとき
このとき、は
に含まれる約数のうちの1つを持ちません。
それをとおくと、
となります。
も
を約数に持たないので、割り切れず、解なしとなります。
以上より、解を持たない時、が示されました。
自分が疑問に感じたのはこれだけです。
次に、Baby-step giant-stepの考え方による解法を書いておきます。
Baby-step giant-stepによる解法
コンテスト当時にtwitterで言及されていたので、解いてみました。
この問題の解は非負整数を用いて、
を求める問題に帰着されます。
ここで、とおきます。
は
で割った商
と余り
を用いて、
とおけます。
なので、
を満たすi,jの組をで全探索できますが、これだと間に合いません。
そこで、式を変形して、
とすると、を含む左辺は右辺の
の影響を受けず一定となります。
従って、予めについて、
を計算し、ハッシュマップなどに記録しておくことで、
について、
と等しいものがあるかをで判定できるようになり、全体で
となります。
実装上、
・を
で割った余りが0でない時は解なしとなり、これは予め判定しておく必要がある。
・で同値なものが複数ある場合、
が最小のもののみ記録する。
という点に気をつけます。
計算量は公式解説より劣りますが、あまり深く考えなくて良いのは楽だと思いました。