コンテスト中に通せたので、自分の解法を書いてみます。 問題 概要 電車が秒で一方の街からもう一方の街に移動し、街に着いたときに秒停車する。高橋君は秒寝て秒起きるを繰り返す。高橋君は街で降車することができるか？もし可能ならば、最短何秒で降車でき…

問題 E - Queen on Grid 行列のマス目がある。左上のマス目をとして、上から番目、左から番目のマス目をマスとする。1手ごとに、そのマスから下、右、右下方向の好きなマスに移動できる。ただし、障害物に移ったり、障害物をを飛び越える移動や、マス目の外…

さて、ここからが本題です。で、とが互いに素とは限らない一般の場合の離散対数問題を解きます。 実験 からの向きに辺を結んでできた有向グラフを考えます。鳩の巣原理より、どのようなについても、少なくとも乗するとより小さい指数乗の値に戻ることがわか…

前回の続きです。一般化されたBSGSはまとまりをよくするために次回に回し、今回は、 Pohlig-Hellman algorithm BSGS, Pohlig-Hellman algorithmの実装 について書いていきたいと思います。 Pohlig-Hellman algorithm を素因数分解したときの指数が大きい場合…