趣旨
マシュマロで記事のお題を募集しております。今回は「$p$進数とガロア拡大体の類似点と相違点」というお題で「素数modを知っているが、$p$進数とガロア拡大体を知らない人向け」に記事を書いてほしいというマシュマロをいただいたので、それに従って記事を書かせていただきます。
なお文脈的に恐らくガロア拡大体はガロア理論のものではなくガロア体の誤植だと思うので、$p$進数体$\mathbb{Q}_p$とガロア体$\mathbb{F}_p$の違いについて解説しようと思います。
また素数modは競技プログラミング界隈で「素数を法とする計算」を広く指す言葉なので、対象も競技プログラミングに興味があって素数modを知っている人を想定していきます。
要約
定義より前に応用を説明しておきます。
まず何らかの整数$X$を$p$で割った余りを求める競技プログラミングの問題に$\mathbb{F}_p$と$\mathbb{Q}_p$と両方が使えます。
$X$の定義に足し算引き算掛け算、そして$p$と互いに素な整数による割り算しか現れない場合、$\mathbb{F}_p$を使えば良いでしょう。
一方で$p$と互いに素とは限らない$0$でない整数による割り算が現れうる場合は$\mathbb{F}_p$が使えないので、$\mathbb{Q}_p$を使いましょう。
例題
例えば以下のような競技プログラミングの問題では$\mathbb{F}_p$が使いにくいので、$\mathbb{Q}_p$を使うと解きやすいと思います。
問題文
正整数$N$と$M$と素数$P$が与えられます。二項係数$\binom{N}{M}$を$P$で割った余りを求めてください。
制約
- $N$は$1 \leq N \leq 10^9$を満たす整数である。
- $M$は$1 \leq M \leq \min \{10^6,N \}$を満たす整数である。
- $P$は$1 \leq P \leq 10^9$を満たす素数である。
実行時間制限 2 sec / メモリ制限 1024 MB
備考
追加で$\min(M,N-M) < P$が制約として課されている場合は$\mathbb{F}_P$を用いるよくある素数modの実装問題となります。
定義
以下$p$は素数を表すとします。
ガロア体$\mathbb{F}_p$
まずガロア体$\mathbb{F}_p$は要素数が$p$である体を指す用語です。要素数が指定されているだけだと一意ではなさそうですが、要素数$p$の体を２つ用意すればそれらの間の同型（同一視）がうまく取れるので、要素数$p$の体が一意でないことはあまり気にする必要がありません。
となるとその文脈で最も扱いやすい「要素数$p$の体」を１つ固定してそれを$mathbb{F}_p$と思うことが通常です。整数論や環論においては特に$\mathbb{Z}/p \mathbb{Z}$という具体的な「要素数$p$の体」が扱いやすいので、それを$\mathbb{F}_p$の定義にすることが多いかと思います。
一方でプログラミングの文脈では組み込み型を直接用いて実装できる概念の方が実用上便利なので、$p$未満の非負整数全体の集合に法$p$での加法と乗法を備えさせたものを$\mathbb{F}_p$の定義と思うのが自然でしょうね。
いずれの流儀でも、環論で広く布教した記法として「環の乗法的単位元をスカラー倍に関して整数$n$倍したもの」を曖昧さの生じない限り$n$と略記するので、計算式の見た目は変わりません。
つまり$\mathbb{F}_p$の乗法的単位元は$1$、加法的単位元は$0$、$1+1$は$2$などと表示することができます。
混乱しやすいところですが、$p = 2$でも$\mathbb{F}_p$において$1+1 = 2$は正しいです。$\mathbb{F}_p$に$2$なんて入っていなさそうな気がするかもしれませんが、「$\mathbb{F}_p$の乗法的単位元をスカラー倍に関して$2$倍したもの」を$2$と略記しているだけなので、$\mathbb{F}_p$において$2$と書かれる要素がきちんとあって、それが$1+1$にほかならないわけです。
例えば$p = 2$の場合、$\mathbb{F}_p$における等式や不等式の例として
\[ \begin{array}{rcl} 0 & \neq & 1 \\
1 & \neq & 2 \\
0 & = & 2 \\
1 & = & -1 \\
0 + 0 & = & 0 \\
0 + 1 & = & 1 \\
1 + 0 & = & 1 \\
1 + 1 & = & 0 \end{array} \]
などが成り立ちます。見ての通り、$\mathbb{F}_p$における等式は表記の上では整数の法$p$における合同式の$\equiv$を$=$に書き直しただけのようなものになります。
というわけで、$\mathbb{F}_p$はmod $p$で全てを考える数体系だと思ってくださって構いません。
$p$進数体$\mathbb{Q}_p$
$p$進数体$\mathbb{Q}_p$は、様々な定義方法がありますが実数と浮動小数点数を知ってい人には$p$進法小数表示を用いた定義が分かりやすいと思います。
まず実数の$p$進法小数表示は、左に有限桁、右に無限桁（途中から先$0$でも良い）の表示となります。また$1$つの実数の$p$進法小数表示は高々$2$通りで、例えば乗法的単位元は$1.000 \cdots$と$0.999 \cdots$の$2$通りのっ表示方法があります。
一方で$p$進数もまた$p$進法小数表示を持つ数体系で、結論から言うと右に有限桁、左に無限桁（途中から先$0$でも良い）の表示を持ち、しかも$1$つの$p$進数の$p$進法小数表示は小数点以下に右端に冗長な$0$つけないという制限のもとで一意です。
表示が一意ということは、結果的に表示そのものを用いて$p$進数という概念が定式化できます。つまり右に有限桁（右端に冗長な$0$つけない）、左に無限桁（途中から先$0$でも良い）$p$進法表示そのものを$p$進数と呼ぶことにすれば良いです。
例えば$p = 2$の場合の$p$進数の具体例は
\[ \begin{array}{r} \cdots 101010 \\
\cdots 111111 \\
\cdots 101010.1 \\
\cdots 111111.1 \end{array} \]
などです。「$\cdots$」にはお好きな$01$無限列を入れてください。
また$p$進数の足し算と引き算と掛け算は$p$進法表記を用いた筆算で直接定義可能です。定義の仕方から、有理数の演算の拡張となることが分かります。特に、整数の演算と整合的です。
$0$でない$p$進数による割り算は掛け算の逆演算として定義します（計算方法は割愛します）。
実数の小数表示を（右に）有限桁で打ち切って近似できることと同様に、$p$進数の小数表示を（左に）有限桁で打ち切って近似できることが可能です。
そして競技プログラミングにおいて特に重要な事実として、非負整数であるような実数や$p$進数に限れば$p$進法表記は小数点なしで最初から有限桁になっているので近似誤差を気にする必要はありません。（もちろん整数でない数同士に演算を適用して結果的に整数が得られる場合は計算過程に誤差が出うる点は注意が必要です）
そして$p$進法表記の$p^0$の位を取り出すことで法$p$での値が求まるので、$p$進数として（分母が$p$と互いに素な）有理数を管理しても法$p$での値を復元可能です。
実装
$\mathbb{F}_p$の実装は言うまでもなく法$p$の演算を用いるだけでよいです。AtCoder Library（ACL）のatcoder::modintなどを参考にしてください。筆者は自作ライブラリを使っていてACLをあまり使ったことがないのでACLについてはよく知りません。
というわけで$\mathbb{Q}_p$の実装に絞って説明いたします。
まず実数を浮動小数点数で実装する際は有限桁に打ち切って
\[ (-1)^{\textrm{符号部}} \times (\textrm{仮数部}) \times 2^{\textrm{指数部}} \]
の形で$3$つのデータで管理しますね。
符号部が$1$bitのデータ、仮数部が非負整数のデータ、指数部が整数のデータです。実際にそれらをどう決めるか（例えば$0$をどう表現するかやケチ表現を行うかなど）やどう管理するか（連続した$64$bitの中で管理するかいくつかのオブジェクトに分けて管理するか）は規格・実装依存となるのであまり気にしないことにしましょう。
同様に$0$でない$p$進数も有限桁で打ち切ると、符号部が不要になり
\[ (\textrm{仮数部}) \times p^{\textrm{指数部}} \]
の形で$2$つのデータで管理することが可能です。
ここで仮数部を何桁まで許すかが近似精度に対応するわけですが、競技プログラミングの文脈で素数modを考えたい場合はしばしば$1$桁だけで十分だったりします。つまり
\[ (p \textrm{未満の非負整数}) \times p^{\textrm{整数}} \]
という形（$1$桁精度）で$p$進数を保持すれば良いです（mod $p$ではなくmod $p^2$などを考えたい時はより多くの桁を保持する必要があります）。
この形で保持された$0$でない$p$進数の同士の積をこの形で表示し直す（近似計算するに）は、仮数部を法$p$で掛け算し、指数部を足し算するだけです。簡単ですね。
例えば$p = 7$だと
\[ (3 \times 7^{8}) \times (5 \times 7^{-6}) \approx 1 \times 7^{2} \]
という感じです。$3 \times 5$がmod $7$で$1$、$8 + (-6)$が$2$ということです。
この乗法を$\mathbb{Q}_p$の$1$桁精度の乗法と便宜的に呼ぶことにしましょう。
足し算や引き算も$1$桁精度であれば指数部の大小比較で簡単に実装できます。精度を上げた場合も指数部を揃えて素数冪modの要領で計算することができます。
また小数点が不要な（小数点以下のない）$p$進数を$p$進整数と言い、その全体を$\mathbb{Z}_p$で表します。$p$進整数のみを扱いたい場合は指数部を$0$に固定して考えればよいので、仮数部だけを考えることになります。
ということは$p$進整数を近似計算するときは単に素数冪を法とする整数を考えるだけになるので、結果的に競技プログラミングでよく使われているものになります。
逆に言うと、$p$進数は素数冪を法とする整数に（素数冪を法とする整数では可逆でない）$p$冪の指数部が追加されたデータとしてみなすことが可能というわけです。
競技プログラミングの累積積で区間積を求める時は群を乗せる必要がありますが、体の乗法モノイドを乗せたい時は$0$の出現頻度を合わせて持つことで群を作って乗せることができましたね。よく見るとこのテクニックとやっていることはほぼ同じです。
応用
二項係数を$p$で割った余りは、$\mathbb{Q}_p$の$1$桁精度の乗法で簡単に求まります。
using ll = long long;
struct Qp
{
static int g_p; // 素数p
int m_n; // 仮数部（p未満の非負整数）
int m_v; // 指数部
// m_n \times ( p^{m_v} )の形でp進数を1桁精度で管理する。
// 整数から構築
inline Qp( int n ) : m_n(n) , m_v(0) {
if( m_n ){
while( m_n % g_p == 0 ){
m_n /= g_p;
++m_v;
}
( m_n %= g_p ) < 0 ? m_n += g_p : m_n;
}
};
// 1桁精度の乗法
inline Qp& operator*=( const Qp& x ) { m_n = ll( m_n ) * x.m_n % g_p; m_v += x.m_v; return *this;}
// 1桁精度の逆元
static Qp Inverse( int i )
{
static vector<int> inv = {0,1};
Qp x{ i };
auto& [n,v] = x;
assert( 0 < n && n < g_p );
int L;
while( ( L = inv.size() ) <= n ){
inv.push_back( inv[g_p%L] * ll( g_p - g_p / L ) % g_p );
}
n = inv[n];
v *= -1;
return x;
}
};
int Qp::g_p = 11;
// binom{n}{m} mod pをQpの1桁精度の乗法で求める。
int Combination( int n , int m )
{
assert( 0 <= m && m <= n );
Qp x{ 1 };
for( int i = 0 ; i < m ; ++i ){
x *= Qp( n - i );
x *= Qp::Inverse( i + 1 );
}
auto& [a,v] = x;
assert( v >= 0 );
return v ? 0 : a;
}
これにて冒頭の問題を計算量$O(\min(M,P))$で解くことができました。
法が素数でない場合は少し工夫が必要です。余力がある人は法$10^8$の二項係数計算問題に挑戦してみましょう：
$\mathbb{F}_p$と$\mathbb{Q}_p$の違い
以上で実感していただけたと思いますが、$p$が$0$か否かが$\mathbb{F}_p$と$\mathbb{Q}_p$の大きな違いの１つです。$\mathbb{Q}_p$では$p$が$0$でないので割り算に使うことが可能です。
また$\mathbb{Q}_p$は解析的議論も適用可能で、$\frac{1}{1+x}$や$\exp(x)$や$\log(x)$などを$x$の収束冪級数で扱ったりNewton法を行ったりすることが可能です。
$p$進解析の競技プログラミング問題：
$\mathbb{Q}_p$の顕著な解析的定理はMahlarの定理です。Mahlarの定理は任意の連続関数$\mathbb{Z}_p \to \mathbb{Q}_p$が二項係数の級数で具体的に表せることを保証します。
例えば多項式関数は連続なのでMahlarの定理を適用可能です。多項式関数にMahlerの定理を適用した結果は「多項式が二項係数の線形結合で具体的に表せる」ということになります。これ自体は競技プログラミング界隈でも有名なようで、二項変換と呼ばれています。
二項変換の競技プログラミング問題：
皆さんも$p$進数が使える競技プログラミングの問題を探したり作ったりしてみましょう。
自分用覚え書き
github pagesで数式を使う際は、閉じ括弧と半角アンダーバーの間に半角スラッシュを入れないとmarkdownからhtmlへの翻訳の仕様でバグるらしい。（波括弧でもたまにバグる）
数式環境をくくる大括弧と数式環境内の中括弧や半角空白や濃度のシャープは半角スラッシュ２つ、改行は半角スラッシュ５つ、その他は基本的に半角スラッシュ１つで良さそう。htmlとmathjaxの関係が難しい。
inline数式内の縦棒はlvertなどを使わないとmarkdownの表と認識される。
大括弧の数式環境はアンパサンドで縦位置を揃えられない。
arrayとalignはどちらも使える。arrayが使えない気がしてしまったのは中括弧につける半角スラッシュの個数を間違えていたから。alignはアンパサンドを等号の右側につけて半角空白を２つ入れると幅がちょうど良さそう。arrayなしだとアンパサンドは使えない。