- \(a \equiv b \pmod n \Leftrightarrow (a - b) \bmod n = 0 \Leftrightarrow n | (a - b)\)
- \(a\bmod n < n\)
- \((a \pm b) \bmod n = ((a \bmod n) \pm (b \bmod n)) \bmod n\)
- \((a \cdot b) \bmod = ((a \bmod n) \cdot (b \bmod n)) \bmod n\)
- \(a \equiv b \pmod n, c \equiv d \pmod n \Rightarrow (a \pm c) \equiv (b \pm d) \pmod n\)
- \(a \equiv b \pmod n, c \equiv d \pmod n \Rightarrow (a \pm c) \equiv (b \pm d) \pmod n\)
- \(ac \equiv bc \pmod n \Rightarrow a \equiv b \pmod{\frac{n}{\gcd(n, c)}}\)
- \(k\in \mathbb{N}_+,a \bmod n = (a \bmod kn) \bmod n\)
- \(k|a,\frac{a}{k} \bmod n = \frac{a \bmod kn}{k}\)
- \(a>n,a \bmod n < \frac{a}{2}\)
- 费马小定理
- 三种方法求逆元
- 龟速乘
定义
模：设 \(a\) 为整数，\(n\) 为正整数，定义
\[a \bmod n = \begin{cases} a - \lfloor \frac{a}{n} \rfloor n & a \geq 0 \\ -(-a \bmod n) & a < 0 \end{cases} \]这与 C++ 中的取模运算符的行为一致。
同余：若，\((a - b) \bmod n = 0\)，则称 \(a\) 与 \(b\) 在模 \(n\) 的意义下同余，记作
\[a \equiv b \pmod n \]\(a \equiv b \pmod n \Leftrightarrow (a - b) \bmod n = 0 \Leftrightarrow n | (a - b)\)
\(a,b\) 均为正整数时，此式等价于 \(a\bmod n = b\bmod n\)
无特别说明，以下与模、同余相关的数均是非负整数。
性质
性质 1
\[a \bmod n < n \]证明：
假设 \(a \bmod n \geq n\)，则
\[\begin{aligned} a \bmod n & \geq n \\ a - \lfloor \frac{a}{n} \rfloor n & \geq n \\ a & \geq n + \lfloor \frac{a}{n} \rfloor n \\ a & \geq n \cdot (\lfloor \frac{a}{n} \rfloor + 1) \\ \frac{a}{n} & \geq \lfloor \frac{a}{n} \rfloor + 1 \\ \end{aligned} \]为 \((1)\) 式。设 \(\frac{a}{n} = x + p, x \in N, p \in [0, 1)\)。则
\[\begin{aligned} \frac{a}{n} & \geq \lfloor \frac{a}{n} \rfloor + 1 \\ x + p & \geq \lfloor x + p \rfloor + 1 \\ x + p & \geq x + 1 \\ p & \geq 1 \end{aligned} \]，与 \(p \in [0, 1)\) 矛盾，故原命题成立。
根据性质 \(1\)，对于 \(a \bmod n\) 可以设 \(a = k \cdot n + z, z < n\)，则 \(z = a \bmod n, k = \lfloor\frac{a}{n}\rfloor\)
性质 2
\[(a \pm b) \bmod n = ((a \bmod n) \pm (b \bmod n)) \bmod n \]证明：
\[\begin{aligned} RHS &= a -\lfloor \frac{a}{n} \rfloor n \pm (b - \lfloor \frac{b}{n} \rfloor n) - \lfloor \frac{a -\lfloor \frac{a}{n} \rfloor n \pm (b - \lfloor \frac{b}{n} \rfloor n) \rfloor}{n} \rfloor n \\ &= a -\lfloor \frac{a}{n} \rfloor n \pm b \mp \lfloor \frac{b}{n} \rfloor n - \lfloor \frac{a -\lfloor \frac{a}{n} \rfloor n \pm b \mp \lfloor \frac{b}{n} \rfloor n}{n} \rfloor n \\ &= a \pm b - \lfloor \frac{a}{n} \rfloor n \mp \lfloor \frac{b}{n} \rfloor n - \lfloor \frac{a \pm b -\lfloor \frac{a}{n} \rfloor n \mp \lfloor \frac{b}{n} \rfloor n}{n} \rfloor n \\ &= a \pm b - n(\lfloor \frac{a}{n} \rfloor \mp \lfloor \frac{b}{n} \rfloor) - \lfloor \frac{a \pm b - n(\lfloor \frac{a}{n} \rfloor \mp \lfloor \frac{b}{n} \rfloor)}{n} \rfloor n \\ &= a \pm b - n(\lfloor \frac{a}{n} \rfloor \mp \lfloor \frac{b}{n} \rfloor) - \lfloor \frac{a \pm b}{n} - (\lfloor \frac{a}{n} \rfloor \mp \lfloor \frac{b}{n} \rfloor) \rfloor n \\ &= a \pm b - n(\lfloor \frac{a}{n} \rfloor \mp \lfloor \frac{b}{n} \rfloor) - \lfloor \frac{a \pm b}{n}\rfloor + \lfloor\lfloor \frac{a}{n} \rfloor \mp \lfloor \frac{b}{n} \rfloor \rfloor n \\ &= a \pm b - n(\lfloor \frac{a}{n} \rfloor \mp \lfloor \frac{b}{n} \rfloor) - \lfloor \frac{a \pm b}{n}\rfloor + (\lfloor \frac{a}{n} \rfloor \mp \lfloor \frac{b}{n} \rfloor) n \\ &= a \pm b - \lfloor \frac{a + b}{n} \rfloor n \\ &= LHS \end{aligned} \]则原命题得证。
性质 3
\[(a \cdot b) \bmod = ((a \bmod n) \cdot (b \bmod n)) \bmod n \]证明：
\[\begin{aligned} RHS &= (a - \lfloor\frac{a}{n}\rfloor n)(b - \lfloor\frac{b}{n}\rfloor n) - \lfloor \frac{(a - \lfloor\frac{a}{n}\rfloor n)(b - \lfloor\frac{b}{n}\rfloor n)}{n} \rfloor n \\ &= ab - \lfloor\frac{a}{n}\rfloor bn - \lfloor\frac{b}{n}\rfloor an + \lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor n^2 - \lfloor \frac{ab - \lfloor\frac{a}{n}\rfloor bn - \lfloor\frac{b}{n}\rfloor an + \lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor n^2}{n} \rfloor n \\ &= ab - \lfloor\frac{a}{n}\rfloor bn - \lfloor\frac{b}{n}\rfloor an + \lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor n^2 - \lfloor \frac{ab}{n} - \lfloor\frac{a}{n}\rfloor b - \lfloor\frac{b}{n}\rfloor a + \lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor n\rfloor n \\ &= ab - \lfloor\frac{a}{n}\rfloor bn - \lfloor\frac{b}{n}\rfloor an + \lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor n^2 - \lfloor\frac{ab}{n}\rfloor n + \lfloor\lfloor\frac{a}{n}\rfloor b \rfloor n + \lfloor\lfloor\frac{b}{n}\rfloor a \rfloor n - \lfloor\lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor n\rfloor n \\ &= ab - \lfloor\frac{a}{n}\rfloor bn - \lfloor\frac{b}{n}\rfloor an + \lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor n^2 - \lfloor\frac{ab}{n}\rfloor n + \lfloor\frac{a}{n}\rfloor bn + \lfloor\frac{b}{n}\rfloor an - \lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor n^2 \\ &= ab - \lfloor\frac{ab}{n}\rfloor n \\ &= LHS \end{aligned} \]则原命题得证。
性质 4
\[a \equiv b \pmod n, c \equiv d \pmod n \Rightarrow (a \pm c) \equiv (b \pm d) \pmod n \]证明：
\( a \equiv b \pmod n \Leftrightarrow n | (a - b) \\ c \equiv d \pmod n \Leftrightarrow n | (c - d) \\ (a \pm c) \equiv (b \pm d) \pmod n \Leftrightarrow n | (a \pm c - (b \pm d)) \\ \because n | (a - b),n | (c - d) \\ \therefore n | ((a - b) \pm (c - d)) \\ \therefore n | ((a \pm b) - (c \pm d)) \\ \therefore (a \pm c) \equiv (b \pm d) \pmod n \)
则原命题得证。
性质 5
\[a \equiv b \pmod n, c \equiv d \pmod n \Rightarrow ac \equiv bd \pmod n \]证明：
\( a \equiv b \pmod n \Leftrightarrow n | (a - b) \\ c \equiv d \pmod n \Leftrightarrow n | (c - d) \\ ac \equiv bd \pmod n \Leftrightarrow n | (ac - bd) \\ \because ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d) \\ 又 n | (a - b), n | (c - d) \\ \therefore n | (ac - bd) \\ 即得 ac \equiv bd \pmod n \)
原命题得证。
性质 6
\[ac \equiv bc \pmod n \Rightarrow a \equiv b \pmod{\frac{n}{\gcd(n, c)}} \]证明：
设 \(g=\gcd(c,n)\)，则有 \(k_1, k_2 \in \mathbb{Z}\) 满足
\(
\begin{cases}
k_1 \cdot g = c \\
k_2 \cdot g = n
\end{cases}
\)
\(ac \equiv bc \pmod n \Leftrightarrow n | c(a-b)\)，即 \(k_2g | k_1g(a - b)\)
则存在 \(q \in \mathbb{Z}\)，满足 \(q \cdot k_2g = k_1g(a-b) \Rightarrow q \cdot k_2 = k_1(a-b)\)，即 \(k_2|k_1(a - b)\)。
\(
\because \gcd(k_1, k_2) = 1 \\
\therefore k_2|(a-b)
\)，即
\(
\frac{n}{\gcd(c,n)}|(a-b) \\
\therefore a \equiv b \pmod{\frac{n}{\gcd(n, c)}}
\)
原命题得证。
性质 7
\[k\in \mathbb{N}_+,a \bmod n = (a \bmod kn) \bmod n \]证明：
\[\begin{aligned} RHS &= a - \lfloor\frac{n}{kn}\rfloor kn - \lfloor\frac{a - \lfloor\frac{n}{kn}\rfloor kn}{n}\rfloor n \\ &= a - \lfloor\frac{n}{kn}\rfloor kn - \lfloor\frac{a}{n} - \lfloor\frac{n}{kn}\rfloor k\rfloor n \\ &= a - \lfloor\frac{n}{kn}\rfloor kn - \lfloor\frac{a}{n}\rfloor n + \lfloor\lfloor\frac{n}{kn}\rfloor k\rfloor n \\ &= a - \lfloor\frac{n}{kn}\rfloor kn - \lfloor\frac{a}{n}\rfloor n + \lfloor\frac{n}{kn}\rfloor kn \\ &= a - \lfloor\frac{a}{n}\rfloor n \\ &= LHS \end{aligned} \]则原命题得证。
性质 8
\[k|a,\frac{a}{k} \bmod n = \frac{a \bmod kn}{k} \]证明：
\[\begin{aligned} RHS &= \frac{a - \lfloor\frac{a}{kn}\rfloor kn}{k} \\ &= \frac{a}{k} - \lfloor\frac{a}{kn}\rfloor n \\ &= \frac{a}{k} - \lfloor\frac{\frac{a}{k}}{n}\rfloor n \\ &= LHS \end{aligned} \]则原命题得证。
性质 9
\[a>n,a \bmod n < \frac{a}{2} \]证明：
\(a = k \cdot n + z, z < n\)，则 \(z = a \bmod n\)。
\[\begin{aligned} z &< n \\ z &< kn \\ 2z &< kn + z \\ 2z &< a \\ z &< \frac{a}{2} \end{aligned} \]即 \(a\bmod n < \frac{a}{2}\)，原命题得证。
模乘法的逆元
定义
设 \(a \in Z, n \in N_+\)，若整数 \(b\)，满足
\[ab \equiv 1 \pmod n \]则称 \(b\) 为 \(a\) 模 \(n\) 的逆元，记 \(b = a^{-1}\)
性质
性质 1
\[对于 aa^{-1}\equiv 1 \pmod n 当且仅当 gcd(a, n) = 1，a^{-1} 才存在。 \]证明：
反证法。假设 \(\gcd(a, n) = g > 1\)，存在 \(a^{-1}\) 满足 \(aa^{-1}\equiv 1 \pmod n\)，则有 \(k_1, k_2\) 满足
\(
\begin{cases}
k_1 \cdot g = a \\
k_2 \cdot g = n
\end{cases}
\)
\( aa^{-1} \bmod n = k_1ga^{-1} \bmod k_2g = k_1ga^{-1} - \lfloor \frac{k_1ga^{-1}}{k_2g} \rfloor k_2g = g(k_1a^{-1} - \lfloor \frac{k_1a^{-1}}{k_2} \rfloor k_2) \)
因为 \(g > 1\)，所以 \(g(k_1a^{-1} - \lfloor \frac{k_1a^{-1}}{k_2} \rfloor k_2) \neq 1\)，即 \(aa^{-1} \bmod n \neq 1\)，与 \(aa^{-1}\equiv 1 \pmod n\) 矛盾，故原命题成立。
性质 2
\[对于 aa^{-1}\equiv 1 \pmod n，若存在 a^{-1}，则 a^{-1} 在模 n 的意义下唯一 \]证明：
设 \(a_1^{-1},a_2^{-1}\) 满足
\(
\begin{cases}
aa_1^{-1} \equiv 1 \pmod n \\
aa_2^{-1} \equiv 1 \pmod n
\end{cases}
\)
则 \(aa_1^{-1} \equiv aa_2^{-1} \pmod n\)，根据模的性质 \(6\) 得 \(a_1^{-1} \equiv a^{-1} \pmod {\frac{n}{gcd(a,n)}}\)，根据同余的性质 \(1\)，得 \(\gcd(a, n) = 1\)，则 \(a_1^{-1} \equiv a^{-1} \pmod n\)，原命题得证。
费马小定理
\[p \in \mathbb{P},a \in \mathbb{N},则 a^p \equiv a \pmod n \]证明：略。
求法
给定 \(a > n\)，求 \(aa^{-1}\equiv 1 \pmod n\)，中的 \(a^{-1}\)
若 \(n \in \mathbb{P}, \gcd(a,n) = 1\)，利用费马小定理，则 \(a^{n-1} \equiv 1 \pmod n \Rightarrow aa^{n-2} \equiv 1 \pmod n\)，\(a^{n-2}\) 即为 \(a^{-1}\)。
求 \(1 \sim n\) 模 \(p\) 意义下的逆元，其中 \(p \in P\)
方法一
对于 \(i \in [1, n] \cap \mathbb{Z}\)
\[\begin{aligned} p \bmod i &= p - \lfloor\frac{p}{i}\rfloor i \\ p \bmod i + \lfloor\frac{p}{i}\rfloor i &= p \\ p \bmod i + \lfloor\frac{p}{i}\rfloor i &\equiv 0 \pmod p \\ \lfloor\frac{p}{i}\rfloor i &\equiv p \bmod i\pmod p \\ \lfloor\frac{p}{i}\rfloor &\equiv \frac{p \bmod i}{i}\pmod p \\ \frac{1}{i} &\equiv \frac{\lfloor\frac{p}{i}\rfloor}{p \bmod i}\pmod p \\ \end{aligned} \]\(\frac{\lfloor\frac{p}{i}\rfloor}{p \bmod i}\) 即为 \(i\) 在模 \(p\) 意义下的逆元。枚举 \(i\)，对于 \(\lfloor\frac{p}{i}\rfloor\) 可以 \(O(1)\) 求出，对于 \(\frac{1}{p \bmod i} \bmod n\)，以为 \(p \bmod i < i\) 所以在求 \(\frac{1}{i} \bmod n\) 之前一定求出来了，\(O(1)\) 调用即可。综上时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)
void calc_inv() {
inv[1] = 1;
for(int i = 2; i <= n; i++)
inv[i] = (((-1ll * (p / i) % p) * inv[p % i]) % p + p) % p;
}
方法二
根据 \(\frac{1}{i!}=\frac{i+1}{(i+1)!}\)，可以按一下方法求 \(1 \sim n\) 的逆元：
- 预处理 \(1 \sim i\) 的阶乘数组，时间复杂度 \(O(n)\)
- 计算 \(n!\) 的逆元，时间复杂度 \(O(\log p)\)
- 从 \(\frac{1}{n!}\) 利用 \(\frac{i}{i!} = \frac{1}{(i-1)!}\)，计算出 \(1 \sim n\) 的阶乘的逆元，时间复杂度 \(O(n)\)
- 求出 \(1 \sim n\) 的逆元 \(\frac{1}{i} \equiv \frac{1}{i!} \cdot (i - 1)! \pmod n\)，时间复杂度 \(O(n)\)
综上时间复杂度 \(O(3n + \log p) = O(n)\)
ll f[N]; // x!
ll g[N]; // (x!)^-1 mod m
ll h[N]; // x^-1
ll quick_pow(ll a, ll p, ll m) {
ll res = 1;
a %= m;
while(p)
{
if(p & 1)
res = (res * a) % p;
a = (a * a) % p;
p >>= 1;
}
return ans % m;
}
void calc(ll n, ll p) {
for(int i=1; i<=n; ++i)
f[i] = f[i - 1] * i % p;
g[n] = quick_pow(f[n], p - 2, p);
for(int i = n - 1; i >= 1; --i)
g[i] = g[i + 1] * (i + 1) % p;
for(int i = 1; i <= n; ++i)
h[i] = g[i] * f[i - 1] % p;
}
若乘法溢出，可以仿照快速幂，写龟速乘：
ll mul(ll a, ll b, ll m) {
ll res = 0;
while(b)
{
if(b & 1)
res = (res + a) % m;
a = (a + a) % m;
b >>= 1;
}
return res % m;
}