https://blog.hamayanhamayan.com/entry/2017/10/14/125941

mod

オイラーの定理
- ECR49 X-mouse in the Campus 解説
逆元計算（フェルマーの小定理）と組合せ計算
- 解説 uwiさんのここに組合せの全てがある
- フェルマーの小定理を使う問題
  - yukicoder No.1140 EXPotentiaLLL! 解説
- 0で除算することは出来ないので注意これ
- yukicoder No.117 組み合わせの数 (二項定理系ライブラリ最強Verify問題)
- AGC025 RGB Coloring 解説
- yukicoder No.573 a^2i = ai 解説
- No.389 ロジックパズルの組み合わせ
- ECR33 Counting Arrays 解説
- 中国人剰余定理
- ABC110 Factorization 解説（nHk）
離散対数問題
- 素数pと定数gと整数yが与えられた時、g^x ≡ y (mod p)を満たすxを求める問題アルゴリズムまとめ tubo28さんの実装例
- yukicoder No.551 夏休みの思い出（２）解説1 解説2 解説3 解説4
- yukicoder No.261 ぐるぐるぐるぐる！あみだくじ！
- AtCoder 乱数調整解説1 解説2
- AtCoder あまり解説
- yukicoder No.251 大きな桁の復習問題(1)
- CSA Fibonacci Mod Baby-Step Giant-Stepで解く
平方剰余
- y,pが与えられて x^2 ≡ y (mod p) を満たすxを求める問題、modsqrtとも言う
- 数学的な知識が必要参考参考
乱択アルゴリズム
- Tonelli–Shanks algorithm
- Cipolla's algorithm
- 離散対数問題の一部と考えると、Baby-step giant-stepアルゴリズムでも解ける
- yukicoder No.551 夏休みの思い出（２）解説1 解説2 解説3 解説4
- CF395 Timofey and remoduling 解説
ウィルソンの定理
(M-1)! ≡ -1 (mod M)という定理がウィルソンの定理解説
- yukicoder No.109 N! mod M
ルーカスの定理【発展的話題】 CRT(中国人剰余定理)とルーカスの定理を使うと解ける二項定理
- 分かりやすいまとめ
- （C(n,m)でn,m≦10^5であれば、違うもっと早い方法があるみたい）この問題のどっかの解説
- 問題
modには大体周期性がある（ほんとか？）
- a^N mod p（pは素数）の周期はp-1
- グラハム数にも周期性がある問題
N! mod MがO(sqrt(M)logM)で計算できるらしい引用元

数学的知識

アルゴリズム
- 繰り返し二乗法による累乗高速化

確率・期待値
- 期待値の線形性

整数問題
- 素数判定
  - O(sqrt(N))の手法
  - ミラーラビン素数判定法
- 素因数分解（Pollard's rho algorithm）
  - 大体O(sqrt(N))の手法を使えばいい
  - ミラーラビンとロー法について
  - POJ Prime Test 解法
  - UVA Factorizing Larget Integers 解法
  - CF Divisions
  - HE Count of paths
  - AC Product and GCD
  - AOJ 約数ゲーム / Divisor Game 解説
  - [https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_f:title=[いろはちゃんコンテスト Day1 Head of The Dragon] 解説
- 約数列挙 O(sqrt(N))
  - 方法
    - 1から順番にNの約数かどうかを見ていく、ある数iがNの約数であれば、N/iも約数となる。
    - ここでi≦N/iが満たされるまでiを見ていくとすると、Nの平方根（sqrt(N)）個分となる
    - これ以上の数はN/iで既にカウントされているので、やらなくていい。
    - 実装例
  - yukicoder No.816 Beautiful tuples 解説
- 高度合成数
  - それ未満のどの自然数よりも約数の個数が大きい自然数
  - これを使う問題はあまり見かけないが、約数の個数があまり多くないから全探索できる理論の担保として見かけたりする
  - 一覧がOEISにある [A002182 - OEIS](https://oeis.org/A002182) [raw](http://oeis.org/A002182/b002182.txt)
  - 一応調べた
    - 10^6以下最大：720720で240個
    - 10^9以下最大：735134400で1344個
    - 10^12以下最大：963761198400で6720個
    - これ以上は約数列挙が難しい
- 素数定理
  - http://www.isc.meiji.ac.jp/~random/lecture/2016-calc1/ishii.html
  - x以下の素数の個数は大体x/logx個
- GCD,LCM
  - ユークリッドの互除法
    - ABC118 Monsters Battle Royale 解説
  - GCDの最悪計算回数はフィボナッチ数列になる
  - ある数aを素因数がある数bの素因数に全て含まれるかをgcdを使って判定することができる問題言及
  - AOJ 電線
  - yukicoder No.736 約比解説
- 平方数
  - 参考
- 互いに素な個数
  - [1,n]でnと互いに素な個数はトーティエント関数
  - [1,n]でgと互いに素な個数はn≦10^6なら包除原理で解けるこれ
- 拡張ユークリッドの互除法
  - ax+by=cの整数解(x,y)を求めるアルゴリズム参考1 参考2 参考3
  - https://yukicoder.me/wiki/拡張ユークリッド互除法
  - SRM735 Div1 Med 解説
自然数をいくつかの自然数の和で表現する系
- ゴールドバッハ予想
  - これ系では一番有名。
  - 『全ての 3 よりも大きな偶数は2つの素数の和として表すことができる』
  - このように自然数を何かの自然数の和で表現するやつは数論で定理とか予想とかがあったりする
- 他一覧
  - 弱いゴールドバッハ予想
    - 『7 より大きい奇数は 3 個の素数の和で表せる』
    - 7より大きい奇数には、素数も含まれるが、これもそれより小さい3つの素数の和で表現可能
  - 多角数定理『すべての自然数は高々 m 個の m 角数の和である』
    - 問題
  - 平方数の和について
    - 二個の平方数の和：素数pが4を法として1に合同 ⇔ 素数p二個の平方数の和で表現可能
    - 三個の平方数の和：３個の平方数の和で表される自然数 | 理系のための備忘録
    - 全ての自然数は高々四個の平方数の和で表される

記数法
- 位取り記数法、N進数
  - 日常的に使ってるのは10進数だし、パソコン内部では2進数だし、プログラマなら16進数もなじみがあるだろう
  - N進数の考え方が分かっていると解きやすい問題も多くある
  - 例外的な考え方もあるが、10進数をN進数に変換した後の形は一意に定まる
- 平衡N進法(Nは3以上の奇数)
  - 例）平衡3進法
  - 通常の3進法では、a_N*3^N+a_{N-1}*3^{N-1}+...+a_0*3^0で、a_iは0,1,2である
  - 平衡3進法では、a_N*3^N+a_{N-1}*3^{N-1}+...+a_0*3^0で、a_iは-1,0,1である
  - 変換方法：[広義の記数法 - Wikipedia](https://ja.wikipedia.org/wiki/%E5%BA%83%E7%BE%A9%E3%81%AE%E8%A8%98%E6%95%B0%E6%B3%95#%E5%8D%81%E9%80%B2%E6%B3%95%E3%81%8B%E3%82%89%E3%81%AE%E5%A4%89%E6%8F%9B%EF%BC%88%E6%95%B4%E6%95%B0%E9%83%A8%E5%88%86%EF%BC%89)
  - （例外的な考え方もあるかは知らないけど、）10進数を平衡N進数に変換した後の形は一意に定まる
  - 問題
    - [平衡三進法カテゴリーの記事一覧 - けんちょんの競プロ精進記録](https://drken1215.hatenablog.com/archive/category/%E5%B9%B3%E8%A1%A1%E4%B8%89%E9%80%B2%E6%B3%95)
    - [No.1106 🦉 何事もバランスが大事 - yukicoder](https://yukicoder.me/problems/no/1106)

加法的関数・乗法的関数
- 一覧
- 乗法的関数
- メビウス関数
  - CF Alex and a TV Show
- トーティエント関数
  - phi(n) := x=[1,n]でgcd(x,n)=1となる数（n以下でnと互いに素な数の個数）
  - ax = 1 (mod m) かつ gcd(a,m) = 1 互いに素の時のxを求められる。(拡張ユークリッドの互除法でも求められる)
  - なぜか出て来る : https://www.hackerrank.com/contests/101hack50/challenges/cutting-the-string/editorial
  - yukicoder No.644 G L C C D M
  - nの素因数をp1,p2,...,pkとすると、phi(n) = n * (1-1/p1)*(1-1/p2)*...*(1-1/pk) CF538 Please, another Queries on Array? 解説
- 数字根
  - ある数Nの桁和（各桁の数字の総和を取ったもの）を1桁になるまで行ったときの最終的な値を数字根という
  - ある数Nを9で割った余りと数字根が一致するという性質がある（ただしNを9で割った余りが0の時は数字根は9か0であり、N=0であるときのみ数字根0となる）
    - 余りが0の部分が問題でコーナーケースとなることが多い
  - この性質を使った検算方法として、九去法というのがある
  - 問題

幾何
- 凸法
- ピックの定理: 格子点（座標がどちらも整数の頂点）の場合の多角形の面積を求める、格子点問題で使える、ほとんど解いてなくて違うの混ざってるかも
  - ARC018 格子点と整数（←ピックの定理は使わないけど、格子点問題として載せとく）
  - HR Integral Points （たぶんピックの定理やるだけ、入門問題）
  - CC Ant Colony 解説
  - AC 三角形と格子点
  - AC Triangles
  - CF313 Randomizer 解説
  - CC Save The Trees 解説
  - CC Needles and Pins 解説
- 三角関数の漸化式
  - cos(N∗X)=2∗cos(X)∗cos((N−1)∗X)−cos((N−2)∗X)という漸化式が立つので行列累乗で高速に計算可能これ解説

組合せ問題
- カタラン数
  - 正しい括弧列はdyck 列やcorrect bracket sequencesとも言うが、その組み合わせ数がカタラン数
  - （の数ー）の数が負にならず、深さ上限もある場合に上手くひっくり返して数え上げるらしい参考
  - 問題と所感
  - AOJ １０歳の動的計画解説（最も初歩的な適用例な気がする）
  - yukicoder No.660 家を通り過ぎないランダムウォーク問題解説（これも初学者向けに悪くない）
  - AOJ Steps 解説（包除原理とかも入ってくる。下限だけでなく上限も制約付き）
  - AGC021 Ball Eat Chameleons 解説（カタラン数っぽいが、境界線が少し違う。考察が重い）
  - CF449 Nephren Runs a Cinema（典型的なカタラン数適用問題らしいが、aCbmod任意がキツイ）
  - HR Brackets Restoring 解説
- 写像12相
  - 資料1 資料2 資料3
  - これらは上手くDPできる場合が多い
  - メモ
  - べき乗和の公式
  - ベル数
    - N個の物を分割する方法の総数参考
    - 「B[n+1]=sum{i=0..n}C(n,k)B[k]」で計算可能
    - http://kmjp.hatenablog.jp/entry/2015/08/12/0930
    - 第2種スターリング数と関連がある
    - σ加法族とベル数の関連性
    - CF315 Symmetric and Transitive 解説
    - B(n,m) := n個の区別する玉をmグループ以下に分割する組合せ　これはO(min(n,m))で計算可能問題
  - 分割数
  - 第一種スターリング数
    - 別解であるが、第一種スターリング数を用いて解答する
    - O(NlogN)で計算できる
    - 類題かも
- ポリアの数え上げ定理
  - http://kmjp.hatenablog.jp/entry/2016/06/05/0930

線形近似
- 最小二乗法で解ける
- yukicoder No.731 等差数列がだいすき解説

近似
- スターリングの公式
- https://mathtrain.jp/stirling
- https://yukicoder.me/problems/no/575

無限級数の誤差評価（筆者未理解）
- 無限級数を答える問題で誤差を埋められないときに考えること
- 問題

多項式と母関数(全然良くわかってない、全く別のも混じってるかも)
- コドフォでrngさんの形式的冪級数紹介
- ラグランジュ補間
  - N+1個の異なる座標がわかっていれば、y=P(x)を復元できる
  - xはどのxでも良いが、高速に計算するにはx=0..Nの座標を使う必要がある
  - O(NlogMOD)くらいで行ける
  - 一般式が多項式で書ける必要がある
  - 問題

- 多項式を利用して解く
  - ARC084 XorShift 解説
    - 多項式上でgcdが行えることを利用する
    - 例えば{18,42,66}から適当な加減を繰り返して作れる数はgcd(18,42,66)=6の倍数となる。なるほど。出典
    - そのため、多項式のgcdをとって、それの整数倍でX以下の組み合わせが答えになる
  - yukicoder No.579 3 x N グリッド上のサイクルのサイズ(hard)
    - かなり難しいっぽい。2変数母関数を作る必要があるらしい
    - 線形漸化式ってなんだろう
  - http://codeforces.com/problemset/problem/168/E?mobile=true
  - http://codeforces.com/problemset/problem/493/E
  - AC Cyclic GCDs
- 母関数を利用した数え上げ
- Formal Power Series (形式的冪級数)　何もわかってない

- 冪乗和を高速に求める
  - ファウルハーバーの公式というのがあり、ベルヌース数を用いる
  - HR Summing the K-N series ファウルハーバーやるだけ問題
  - yukicoder No.665 Bernoulli Bernoulli ファウルハーバー
  - ECR7 The Sum of the k-th Powers ファウルハーバーじゃ間に合わない？
  - HR Highway Construction ファウルハーバー+二項定理による分解
  - 冪乗和はファウルハーバーよりより良い方法があるかも
  - 以下、その他
  - https://erdos.sdslabs.co/problems/7 解説
  - https://www.codechef.com/FEB16/problems/WRDSUM 出典
  - https://www.codechef.com/problems/SFUNC
- 微分を使って解く
  - 二項係数×冪乗の総和を微分を使ってとく問題
- 未解決
  - KEYENCE Programming Contest 2019 F - Paper Cutting（期待値？）

数列
- 完全順列、モンモール数
  - 参考1 参考2 参考3
  - モンモール数の漸化式を使う問題
  - 完全順列を題材とした問題
    - AOJ Derangement 解説1 解説2
    - CF PolandBall and Gifts 解説

写像
- 順列は写像と考えて解く典型がある参考
- ABC013 阿弥陀 http://kakira.hatenablog.jp/entry/2014/09/16/201532:titlte=解説
- AOJ SolveMe 解説1 解説2 解説3
- AGC031 A Sequence of Permutations

関数合成
- こっちにaddとmaxの関数合成使ってるものがある
- min,max,addは関数合成可能
  - ABC196E Filters

メモ
- (x-a1)^2+(x-a2)^2+...の効率的な計算方法
  - (X-x1)^2+(X-x2)^2+...+(X-x_n)を展開するとnX^2-2*X*(x1+x2+..xn)+(x1^2+x2^2+...+xn^2)となり、xの総和とxの二乗の総和から高速計算が可能
  - yukicoder No.1099 Range Square Sum

競技プログラミングにおける数学的問題まとめ

関連記事

mod

数学的知識