問題 Baby-step giant-stepによる解法とWeb公式解説の理解メモ 公式解説の理解 をで割って良い理由 の時に解なしになる理由 Baby-step giant-stepによる解法 公式解説の理解 公式解説 をで割って良い理由 とします。 を変形し、 とします。 はの倍数となる必…

はじめに 離散対数問題についての問題がAtCoder Beginner Contestで出題され、色々と調べてみたので、その内容をメモします。 離散対数問題 を満たす最小の整数kを求める問題です。 これを求めるアルゴリズムにBaby-step giant-stepがあります。 Baby-step G…

解説なしAC はレプユニット数という呼ばれ、その一般項はなので、この問題の一般項はです。 2や9を無視できれば、を求める問題になり、フェルマーの小定理などで解けそうという感じなので、2と9をどうにかします。 とします。 Kに2を含む場合 XがKの倍数であ…