離散対数問題とは 整数 に対して, を満たす最小の非負整数 を求める問題です. 例えば のとき, より が解となります. Baby-step Giant-stepアルゴリズム 底 と mod が互いに素なときに使える離散対数問題の 解法です. とします. とおくと, となります. したが…

概要 清一色のシャンテン数は01BFSで計算できる。 機械的な計算なので、正当性が簡単に証明できる。 シャンテン数とは テンパイするまでに必要な牌の最小枚数のこと。 例えば のとき、 を引いてを捨てればテンパイとなる。これより少ない枚数の入れ替えでテ…

概要 mod Rolling Hash が任意の基数で落ちる（数列比較の）問題が作れた。 基数を2つとってハッシュのペアで比較するか、もっと大きいmodを使おう。 Rolling Hashとは 文字列や整数列に対するハッシュ関数の一つ。以下では整数列のみを扱う。 法 と基数 を…