「整数論テクニック集」を、pdfとして公開しました。整数論の問題を解くときに必要なテクニックを体系的にまとめた文章です。AtCoder のレーティングが水色から赤下位程度の方を、対象読者にしています。

概要 ダイクストラ法を使うと、単一始点 s から全ての頂点への最短距離が計算できるのは有名だね。これを少し拡張することで、「s からの最短距離と、それを実現する最短経路の個数」の組を、全ての頂点について計算することができるわ。 詳しく 少し天下り…