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

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

要約 この記事では、Garner のアルゴリズムについての話、およびその Java 実装と、それが多倍長整数の計算量削減にどう使えるのかを解説するわ。 前提知識 中国剰余定理 中国の剰余定理 - Wikipedia について知っていることを前提にするわ。また、多倍長整…