整数論テクニック集
1 基本: アルゴリズムについて 2
1.1 アルゴリズムにおける不変量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 mod p 上の計算 (モジュラー演算) 3
2.1 基本: 整数の加減乗除 (Lv. 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 基本: 逆元 (Lv. 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 基本: 分数の加減乗除 (Lv. 2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 二分累乗法 (Lv. 1) 5
3.1 モノイド的構造を見つけて二分累乗する (Lv. 2) . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 うまい変形で除算を回避する (Lv. 2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4 Abundance で殴る (Lv. 2) 9
4.1 素数の abundance で殴る (Lv. 2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5 mod p のアルゴリズム 9
5.1 基礎知識 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.2 mod sqrt, Tonelli-Shanks のアルゴリズム (Lv. 3) . . . . . . . . . . . . . . . . . . . . . . . . . 10
6 群論 (Lv. 4) 14
6.1 群 (Lv. 4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
7 平方剰余の相互法則と 2 次体 (Lv. 4) 15
7.1 ルジャンドル記号 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
7.2 平方剰余の相互法則 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7.3 2 次体 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7.4 有限体 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.5 フロベニウス写像 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.6 応用例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
8 mod p のアルゴリズム その 2 18
8.1 mod sqrt その 2, Lehmer のアルゴリズム (Lv. 3) . . . . . . . . . . . . . . . . . . . . . . . . . 18
8.2 mod sqrt その 3, Cipolla のアルゴリズム (Lv. 4) . . . . . . . . . . . . . . . . . . . . . . . . . 21
9 多項式を使うテク (Lv. 4) 22
9.1 高速フーリエ変換 (FFT) (Lv. 3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
9.2 フェルマーの小定理 (Lv. 3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
9.3 巡回群構造を用いた特殊な畳み込み (Lv. 4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
9.4 1 の 2^k 乗根 mod p を用いた畳み込み . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
10 ペル方程式 (Lv. 4) 31
11 単項イデアル整域 (Lv. 5) 33
Related Pages
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁dp×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×bit×binary-trie×convex-hull-trick-add-monotone×li-chao-tree×link-cut木_部分木クエリ×link-cut木×ウェーブレット行列×スパーステーブル×スライド区間の昇順k個の和×セグメント木×トライ木×マージ可能ヒープ×列の平方分割×平衡二分探索木×永続配列×素集合データ構造×unionfind×ローリングハッシュ×接尾辞配列×最長共通接頭辞×最長回文×回文×複数文字列検索×hl分解×全方位木dp×最小共通祖先×木の直径×木の重心分解×根付き木に変換×mod-pow×オイラーのφ関数×オイラーのφ関数テーブル×ベル数×ラグランジュ補間×二項係数×二項係数テーブル×任意mod畳み込み×分割数×分割数テーブル×商列挙×形式的冪級数×形式的べき級数×拡張ユークリッドの互除法×拡張ユークリッド互除法×第2種スターリング数×約数列挙×素因数分解×素数テーブル×素数判定×組合せ×行列演算×進数変換×階乗×離散対数問題×高速フーリエ変換×divide-and-conquer-optimization×monotone-minima×スライド最小値×一次元累積和×二次元累積和×個数制限付きナップサック×最大長方形×最適二分探索木×最長増加部分列×ダブリング×包除原理×燃やす埋める問題×燃やす埋める×牛ゲー×mo’s_algorithm×offline-dynamic-connectivity×座標圧縮×アルゴリズム→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]