Rosmarinus の 奇妙数论学习笔记

· · 个人记录

介绍

简单概括一下情况的话就是 CSP 和 NOIP 近在眼前但是 Rosmarinus 有关数论的部分几乎全部不会……所以 Ros 痛并思痛下定决心苦学数论。

也是因为前段时间在 Luogu 里发帖求资料下面只有一堆铜球所以干脆自己写一个。

这里的内容会随着 Ros 的学习进度不断更新，虽说主要是给自己看的但是我也会尽量让大家都能看懂（请相信我的教学水平），所以这是一个造福社会的东西。

前面的内容可能会比较简单。

目录

感谢名单

感谢来自 @Sya_Resory、@dengziyue、@GuidingStar、@lzxxzl 等大佬的指正。

同余

定义

对于类似于 a\equiv b\pmod{m} 的式子为同余方程，读作「a 与 b 在模 m 意义下同余」。

含义

## 性质 - 反身性：$a\equiv a\pmod m$； - 对称性：若 $a\equiv b\pmod{m}$，则 $b\equiv a\pmod{m}$； - 传递性：若 $a\equiv b\pmod{m}$，$b\equiv c\pmod{m}$，则 $a\equiv c\pmod{m}$； - 相加：若 $a\equiv b\pmod{m}$，$c\equiv d\pmod{m}$，则 $a\pm c\equiv b\pm d\pmod{m}$； - 相乘：若 $a\equiv b\pmod{m}$，$c\equiv d\pmod{m}$，则 $ac\equiv bd\pmod{m}$； - 相除：若 $ac\equiv bc\pmod{m}$，则 $a\equiv b\pmod{\frac{m}{\gcd(c,m)}}$； 特殊的，若 $\gcd(c,m)=1$，则 $a\equiv b\pmod{m}$。 相对地，若 $\gcd(c,m)=1$，$a\equiv b\pmod{m}$，则 $ac\equiv bc\pmod{m}$。 - 幂运算：若 $a\equiv b\pmod{m}$，则 $a^n\equiv b^n\pmod{m}$； - 若 $a\equiv b\pmod{m_i}$（$1\le i\le n$），则 $a\equiv b\pmod{[m_1,m_2,\dots,m_n]}$，其中 $[m_1,m_2,\dots,m_n]$ 表示 $m_1,m_2,\dots,m_n$ 的最小公倍数。 # 逆元 ## 定义 若对于正整数 $a,b,x$ 满足 $\frac{a}{b}\equiv a\times x\pmod{m}$，则称 $x$ 为 $b$ 的逆元，记作 $b^{-1}$（注意，在这里 $b^{-1}$ 不是 $b$ 的负一次方，$b^{-1}$ 是一个整数） ## 性质 $b\times b^{-1}\equiv 1\pmod{m}

对原式进行移项即可

求法

b^{-1}\pmod p=b^{p-2}\bmod p

具体证明请见「费马定理」

说说我对逆元的理解

如你们所见，b^{-1} 在我们之前的学习中代表着 b 的倒数，也就是 \frac{1}{b}

那为什么在这里又不一样了呢？

其实你可以尝试类比一下：

但是呢？在同余系（我不知道是不是叫这个名字的）的定义域为 Z，也就是说是不能出现小数的。

但是啊，在同余系中，我们虽然不可以使用 a\div b，但是我们可以使用 a\times b^{-1}。

所以，共同点：

所以啊，逆元其实就是同余系中的除法。

提一嘴，我们的编程老师：「纯粹的除法可是一个很稀有的东西！」

所以说，当我们今后遇到一个带有除法的需要取模的式子，只要将除 a 转化为乘 a 的逆元即可正常操作。

质数

定义

质数和合数是针对所有大于 1 的「自然数」来定义的（所有小于等于 1 的数都不是质数）。

所有小于等于 1 的整数既不是质数也不是合数。

质数的判定——试除法：

一个合数的约数总是成对出现的，如果 $d|n$，那么 $(n\div d)|n$，因此我们判断一个数是否为质数的时候，只需要判断较小的那一个数能否整除 $n$ 就行了，即只需枚举 $d\le(n\div d)$，即 $d\times d\le n$，$d\le \sqrt{n}$ 就行了。 `sqrt(n)` 这个函数执行的时候**比较慢**。 ### 代码： ```cpp bool is_prime(int x) { if(x < 2) return false; for(int i = 2; i <= x / i; i ++) // x / i 是最快且最不容易爆炸的写法 { if(x % i == 0) return false; } return true; } ``` ## 分解质因数——试除法（算数基本定理） 算数基本定理：任何一个大于 $1$ 的自然数 $n$，如果 $n$ 不为质数，那么 $n$ 可以唯一分解成有限个质数的乘积 $n=P_1^{a_1}P^{a_2}_2P^{a_3}_3\dots P^{a_k}_k$，这里 $P_1<P_2<P_3<\dots <P_k$ 均为质数，其中指数 $a_i$ 是正整数。 特别要注意——分解质因数与质因数不一样，分解质因数是一个过程，而质因数是一个数。 一个合数分解而成的质因数最多只包含一个大于 $\sqrt{n}$ 的质因数。（反证法，若 $n$ 可以被分解成两个大于 $\sqrt{n}$ 的质因数，则这两个质因数相乘的结果大于 $n$，与事实矛盾） 当枚举到某一个数 $i$ 的时候，$n$ 的因子里面已经不包含 $[2,i−1]$ 里面的数（已经被除干净了），如果 $n | i$，则 $i$ 的因子里面也已经不包含 $[2,i−1]$ 里面的数，因此每次枚举的数都是质数。 质因子（质因数）在数论里是指能整除给定正整数的质数。根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。 两个没有共同质因子的正整数称为互质。因为 $1$ 没有质因子，$1$ 与任何正整数（包括 $1$ 本身）都是互质。 只有一个质因子的正整数为质数。 ### 代码： ```cpp void divide(int x) { for(int i = 2; i <= x / i; i ++) { if(x % i == 0) { int s = 0; while(x % i == 0) x /= i, s ++ ; cout << i << ' ' << s << endl; } } if (x > 1) cout << x << ' ' << 1 << endl; // 大于sqrt(n)的数 cout << endl; } ``` ## 筛质数（朴素筛法） 步骤：把 $[2,n−1]$ 中的所有的数的倍数都标记上，最后没有被标记的数就是质数。 原理：假定有一个数 $p$ 未被 $[2,p−1]$ 中的数标记过，那么说明，不存在 $[2,p−1]$ 中的任何一个数的倍数是 $p$，也就是说 $[2,p−1]$ 中不存在 $p$ 的约数，因此，根据质数的定义可知：$p$ 是质数。 调和级数：当 $n$ 趋近于正无穷的时候，$\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\dots+\frac{1}{n}=\ln n+c$（$c$ 是欧拉常数，约等于 $0.577$ 左右） 时间复杂度：约为 $O(n\log n)$（注：此处的 $\log$ 特指以 $2$ 为底） ## 埃氏筛（稍加优化版的筛法） 质数定理：$1\sim n$ 中有 $n\ln n$个质数。 步骤：在朴素筛法的过程中只用质数项去筛。 时间复杂度：$O(n\log(\log n))$。 ### 代码： ```cpp int primes[N], cnt; // primes[] 存储所有素数 bool st[N]; // st[x] 存储 x 是否被筛掉 void get_primes(int n) { for(int i = 2; i <= n; i ++) { if(st[i]) continue; primes[cnt ++] = i; for(int j = i + i; j <= n; j += i) st[j] = true; } } ``` ## 线性筛 若 $n\approx10^6$，线性筛和埃氏筛的时间效率差不多，若 $n\approx10^7$，线性筛会比埃氏筛快了大概一倍。 核心：$1\sim n$ 内的合数 $p$ 只会被其最小质因子筛掉。（算数基本定理） 原理：$1\sim n$ 之内的任何一个合数一定会被筛掉，而且筛的时候只用最小质因子来筛，然后每一个数都只有一个最小质因子，因此每个数都只会被筛一次，因此线性筛法是线性的。 枚举到 $i$ 的最小质因子的时候就会停下来，即 `if(i % primes[j] == 0) break;` 当 `i % primes[j] != 0` 时，`primes[j]` 一定小于 $i$ 的最小质因子，`primes[j]` 一定是 `primes[j]*i` 的最小质因子。 当 `i % primes[j] == 0` 时，`primes[j]` 一定是 $i$ 的最小质因子，而 `primes[j]` 又是 `primes[j]` 的最小质因子，因此 `primes[j]` 是 `primes[j]*i` 的最小质因子。 ### 代码 ```cpp int primes[N], cnt; // primes[]存储所有素数 bool st[N]; // st[x]存储x是否被筛掉 void get_primes(int n) { for(int i = 2; i <= n; i ++) { if(!st[i]) primes[cnt ++] = i; // j < cnt 不必要，因为 primes[cnt - 1] = 当前最大质数 // 如果 i 不是质数，肯定会在中间就 break 掉 // 如果 i 是质数，那么 primes[cnt - 1] = i，也保证了 j < cnt for(int j = 0; primes[j] <= n / i; j ++) { st[primes[j] * i] = true; if(i % primes[j] == 0) break; } } } ``` # 约数 ## 试除法求所有约数 ### 代码 ```cpp int divisors[N], cnt; // divisors[] 存储所有约数 void get_divisors(int x) { for(int i = 1; i <= x / i; i ++) { if(x % i == 0) { divisors[++ cnt] = i; // 约数总是成对出现 if(i * i != n) divisors[++ cnt] = n / i; // 需要判断是否重复 } } } ``` ## 求一个数所有的约数个数 ### 公式 若 $n=P_1^{a_1}P^{a_2}_2P^{a_3}_3\dots P^{a_k}_k$，则 $n$ 的约数个数为 $(a_1+1)(a_2+1)(a_3+1)\dots(a_k+1)$。 - 证明 对于任意一个 $n$ 的约数 $m$，$m=P_1^{b_1}P^{b_2}_2P^{b_3}_3\dots P^{b_k}_k$，$0\le b_i\le a_i$ 均成立，因此 $m$ 的个数就是 $b_i$ 的所有可能的取法的个数，且 $b_i$ 的不同取法对应的 $m$ 均不相同。 ### 小知识 在 `int` 范围内，约数个数最多的数的约数个数约为 $1500$ 个。 ### 代码 ```cpp const int MOD = 1e9 + 7; void get_divisors_num(int x) // 求 x 的约数个数 { unordered_map<int, int>primes; for(int i = 2; i <= x / i; i ++) { while(x % i == 0) { primes[i] ++; x /= i; } } if(x > 1) primes[x] ++; long long ans = 1; for(auto prime : primes) ans = ans * (prime.second + 1) % MOD; // 一个神奇的能够遍历 map 中所有元素的写法 cout << ans << endl; } ``` ## 求一个数所有约数的和 ### 公式 若 $n=P_1^{a_1}P^{a_2}_2P^{a_3}_3\dots P^{a_n}_n$，则 $n$ 的所有约数的和为 $$(P_1^{0}+P_1^1+P_1^2+\dots+P_1^{a_1})(P_2^{0}+P_2^1+P_2^2+\dots+P_2^{a_2})\dots(P_k^{0}+P_k^1+P_k^2+\dots+P_k^{a_k})$$ ### 代码 ```cpp const int MOD = 1e9 + 7; void get_divisors_sum(int x) // 求 x 的所有约数的和 { unordered_map<int, int>primes; for(int i = 2; i <= x / i; i ++) { while(x % i == 0) { primes[i] ++; x /= i; } } if(x > 1) primes[x] ++; long long ans = 1; for(auto prime : primes) { int p = prime.first, a = prime.second; long long t = 1; for(int i = 1; i <= a; i ++) t = (t * p + 1) % MOD; // 为什么可以这么写，自己证吧 ans = ans * t % MOD; } cout << ans << endl; } ``` ## 欧几里得算法（辗转相除法） ### 小性质 1 若 $d | a$，$d | b$，则 $d|(a+b)$，$d|(ax+by)$。不证。 ### 小性质 2 $\gcd(a,b)=\gcd(b,a\bmod b)$。 - **证明**： $a\bmod b=a-\lfloor \frac{a}{b}\rfloor\times b$； 设 $c=\lfloor \frac{a}{b}\rfloor$，则有 $a\bmod b=a-c\times b$； 设 $(a,b)$ 的任意一个公约数为 $x$，即 $x|a$，$x|b$； $\therefore x|b$，$x|a$，$x|(c\times b)$； $\because a>c\times b$； $\therefore x|(a-c\times b)$； $\therefore (a,b)$ 的任意一公约数，都是 $(b,a-c\times b)$ 的公约数，即左右两者等价； $\therefore \gcd(a,b)=\gcd(b,a-c\times b)$； 即：$\gcd(a,b)=\gcd(b,a\bmod b)$； 证毕。 ### 代码 ```cpp int gcd(int a, int b) // 求 a, b 的最大公约数 { return b ? gcd(b, a % b) : a; } ``` # 欧拉函数 ## 定义 $\varphi(n)$ 表示 $1\sim n$ 中与 $n$ 互质的数的个数。 如 $\varphi(6)=2$，分别为 $1,5$。 特别的，$\varphi(1)=1$。 ## 公式 设 $n=P_1^{a_1}P_2^{a_2}P_3^{a_3}\dots P_k^{a_k}$，则 $\varphi(n)=n(1-\frac{1}{P_i})(1-\frac{1}{P_2})(1-\frac{1}{P_3})\dots(1-\frac{1}{P_k})$。 ## **证明** 已知： - $\varphi$ 为积性函数，即若 $\gcd(a,b)=1$，$\varphi(a\times b)=\varphi(a)\times\varphi(b)$； 不会证，记结论吧。 - 对于任意一质数 $p$，$\varphi(p)=p-1$； 由质数的定义可得。 - 对于任意一质数 $p$，$\varphi(p^a)=p^a-\frac{p^a}{p}=p^a-p^{a-1}=p^a(1-\frac{1}{p})$ ； 由于 $p$ 是质数，所以 $p^a$ 只有 $p$ 一个质因数，则在 $1\sim p^a$ 的范围内，只有 $p,2p,3p,\dots,\frac{p^a}{p}$ 这 $p^{a-1}$ 个数与 $p^a$ 不互质。因此，根据定义得，$\varphi(p^a)=p^a-\frac{p^a}{p}=p^a(1-\frac{1}{p})$。 因此，对于 $n=P_1^{a_1}P_2^{a_2}\dots P_k^{a_k}$： $$\varphi(n)=\varphi(p_1^{a_1})\varphi(p_2^{a_2})\dots\varphi(p_k^{a_k})=P_1^{a_1}(1-\frac{1}{P_1})P_2^{a_2}(1-\frac{1}{P_2})\dots P_k^{a_k}(1-\frac{1}{P_k})=n(1-\frac{1}{P_i})(1-\frac{1}{P_2})\dots(1-\frac{1}{P_k})$$ 证毕。 ## 代码 ```cpp void get_phi(int x) // 求 phi(x) { if(x == 1) { cout << "1\n"; return; } int res = x; for(int i = 2; i <= x / i; i ++) { if(x % i == 0) { res = res / i * (i - 1); while(x % i == 0) x /= i; } } if(x > 1) res = res / x * (x - 1); cout << res << endl; } ``` ## 线性筛 欧拉函数线性筛能够在 $O(n)$ 的时间内求出 $\varphi(1)\sim \varphi(n)$。 代码仅仅是在线性筛筛质数的情况下增加了几句话。 **先上代码**： ```cpp int primes[N], cnt; // primes[]存储所有素数 int phi[N]; bool st[N]; // st[x]存储x是否被筛掉 void get_phi(int n) { phi[1] = 1; // 特殊规定 for(int i = 2; i <= n; i ++) { if(!st[i]) { primes[cnt ++] = i; phi[i] = i - 1; // 质数的性质 } for(int j = 0; primes[j] <= n / i; j ++) { st[primes[j] * i] = true; if(i % primes[j] == 0) { phi[i * primes[j]] = phi[i] * primes[j]; // 注释 1 break; } phi[i * primes[j]] = phi[i] * (primes[j] - 1); // 注释 2 } } } ``` - **注释 $1$**： 令 `primes[j]` 的值为 $p$，显然 $p$ 为质数。 则在 `i % primes[j] == 0` 时，即 $p|i$，此时，$i$ 与 $i\times p$ 的质因数完全相同。 由于 $\varphi(n)$ 仅与 $n$ 的质因数本身，与 $n$ 的质因数次数无关，因此 $\varphi(i\times p)=\varphi(i)\times p$（用言语完全无法表述清楚，请读者自行思考）。 - **注释 $2$**： 令 `primes[j]` 的值为 $p$，显然 $p$ 为质数。 则在此时，$\gcd(i,p)=1$，即 $i,p$ 互质。 根据积性函数定义，$\varphi(i\times p)=\varphi(i)\times \varphi(p)=\varphi(i)\times(p-1)$。 # 欧拉定理 ## 内容 若 $\gcd(a,n)=1$，即 $a$ 与 $n$ 互质，则 $a^{\varphi(n)} \equiv 1\pmod{n}$。 ## 证明 设在 $1\sim n$ 中，所有与 $n$ 互质的数分别为 $x_1,x_2,\dots, x_{\varphi(n)}$。 则在 $ax_1,ax_2,\dots,ax_{\varphi(n)}$ 中，不存在 $ax_i$ 与 $ax_j$，$ax_i\equiv ax_j\pmod{n}$。 - 证明： 若存在 $ax_i\equiv ax_j\pmod{n}$，则 $a(x_i-x_j)\equiv 0\pmod{n}$；（同余性质） 由于 $\gcd(a,n)=1$，故 $x_i-x_j\equiv 0\pmod{n}$； 则 $x_i\equiv x_j\pmod{n}$； 则 $x_i=x_j$； 与现实矛盾。 故不存在 $ax_i\equiv ax_j\pmod{n}$，即 $ax_1,ax_2,\dots,ax_{\varphi(n)}$ 在模 $m$ 意义下互不相同。 因此，$x_1,x_2,\dots, x_{\varphi(n)}$ 与 $ax_1,ax_2,\dots,ax_{\varphi(n)}$ 在模 $m$ 意义下为顺序不同的同一组数； 因此，$a^{\varphi(n)}\times x_1x_2\dots x_{\varphi(n)}\equiv x_1x_2\dots x_{\varphi(n)}\pmod{n}$； 因此，$a^{\varphi(n)}\equiv 1\pmod{n}$。 # 快速幂 虽然这个应该不算数论但是应该也问题不大吧？ ## 前置知识 $a^{x1}\times a^{x2}=a^{x_1+x_2}$（初中数学） ## 思路 对于 $a^b$（$b$ 是一个很大的数），将 $b$ 转化为二进制，即 $b=2^{x_1}+2^{x_2}+\dots+2^{x_k}$，我们只需要算出 $a^{2^{x_1}}a^{2^{x_2}}\dots a^{2^{x_k}}$ 即可。 时间复杂度：$O(\log n)$。 ## 代码 ```cpp const long long N = 1e9 + 7; void quick_mi(long long a, long long b) // 求 a ^ b % MOd { long long t = a, ans = 1; while(b) { if(b % 2 == 1) ans = ans * t % MOD; // b & 1 即为 b % 2 == 1，但是速度会快一点 t = t * t % MOD; b /= 2; } cout << ans % MOD << endl; } ``` ## 例题：快速幂求逆元 ### 题目描述 给定 $b,p$，其中 $p$ 是质数，求 $b$ 在模 $p$ 意义下的乘法逆元。 ### 前置知识 费马定理：若 $\gcd(b,p)=1$，则 $b^{p-1}\equiv 1\pmod{p}$。 ### 具体做法 由于 $p$ 为质数，因此： - 若 $p|b$，则一定不存在逆元； - 否则，$\gcd(b,p)=1$。 因此，$b^{p-1}\equiv 1\pmod{p}$，即 $b\times b^{p-2}\equiv 1\pmod{p}$。 因此，$b^{p-2}\bmod p$ 即为我们要求的逆元。 ### 代码 略。 # 裴蜀定理 对于任意一对正整数 $a,b$，一定存在**非零整数** $x,y$ 满足 $ax+by=\gcd(a,b)$，同时 $\gcd(a,b)$ 是满足条件的 $ax+by$ 的最小正整数和。 - 证明 设 $ax+by=d$，$d\in N^{+}$ 则 $\gcd(a,b)|d$； - 证明：由于 $\gcd(a,b)|a$，$\gcd(a,b)|b$，因此 $\gcd(a,b)|ax+by$，即 $\gcd(a,b)|d$。 因此，$\gcd(a,b)$ 一定是最小正整数和。 关于存在性证明请见扩展欧几里得算法。 # 扩展欧几里得算法 ## 本体 ### 直接上代码： ```cpp int exgcd(int a, int b, int &x, int &y) // 求出 ax + by = gcd(a, b) 的一组可行解 { if(!b) { x = 1, y = 0; // 当 b = 0 时，显然 x = 1, y = 0 就是一组可行解 return a; } int d = exgcd(b, a % b, y, x); // 注释 1 y -= a / b * x; return d; } ``` ### 注释 1 因为 $a,b$ 翻转了所以我们把 $x,y$ 也翻转一下； 在此次递归结束后，应当有：$by+(a\bmod b)x=d$； 即为： $by+(a-\lfloor\frac{a}{b}\rfloor b)x=d$； 又为：$ax+b(y-\lfloor\frac{a}{b}\rfloor x) = d$； 因此，令 $y=y-\lfloor\frac{a}{b}\rfloor x$，就又回到了原来的式子：$ax+by=d$。 一直递归即可求出最终解。 ## 关于裴蜀定理 由以上代码得，一定能返回一组可行解。 因此，裴蜀定理成立。 而对于 $ax+by=d$，有解的充要条件为 $\gcd(a,b)|d$。 ## 例题：线性同余方程 ### 题目描述 给定正整数 $a,b,m$，求出一个 $x$ 满足 $ax\equiv b\pmod{m}$。 ### 思路分析 对式子做一些变形： $\exist y\in Z$，使得 $ax=my+b$； 即为：$ax-my=b$； 设 $y'=-y$，则 $ax+my'=b$； 有解的充要条件为：$\gcd(a,m)|b

代码

略。

中国剩余定理

内容

给定 k 个两两互质的整数 m_1,m_2,\dots,m_k，我们需要解决如下线性同余方程组：

\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\\dots\\x\equiv a_k\pmod{m_k}\end{cases}

令 M=m_1m_2\dots m_k，M_i=\frac{M}{m_i}，M_i^{-1} 表示 M_i 在模 m_i 意义下的逆元。

则有：x=a_1M_1M_1^{-1}+a_2M_2M_2^{-1}+\dots + a_kM_kM_K^{-1}。

证明

暂时不会。

先挖个坑。

组合数

定义

C_a^b=\dfrac{a!}{b!(a-b)!}

表示在 a 个数中取 b 个数的方案数。

公式

C_a^b=C_{a-1}^b+C_{a-1}^{b-1}

证明

可以换个角度证明，若我们在做一道题目，用 dp_{i,j} 表示从 i 个苹果中取 j 个的方案数，稍微思考一下就可以推出：dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}。都在学数论了这个应该能明白。

例题

题目描述

给定 T （1\le T\le 10^5）组询问，每组询问给定两个正整数 a,b（1\le b\le a\le 10^5），求 C_{a}^{b}\bmod(10^9+7)。

思路分析

考虑到数据范围，预处理出所有 C_a^b 不太现实，因此我们考虑另外一种做法：

若要求：C_a^b\bmod p，即 \dfrac{a!}{b!(a-b)!}

设 fact(i)=i!，infact(i)=(i^{-1})!

则 C_a^b\bmod p=fact(a)\times infact(b)\times infact(a-b)

时间复杂度：$O(n\log n)

代码

#define LL long long
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;
int fact[N], infact[N];
int qmi(int a, int k, int p) // qmi = quick_mi，快速幂
{
    int ans = 1;
    while(k)
    {
        if(k & 1) ans = (LL)ans * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return ans;
}

void pre() // 预处理
{
    fact[0] = infact[0] = 1; // 边界
    for(int i = 1; i <= N; i ++) fact[i] = (LL)fact[i - 1] * i % MOD;
    for(int i = 1; i <= N; i ++) infact[i] = (LL)infact[i - 1] * qmi(i, MOD - 2, MOD) % MOD; // 费马定理
}

void Work()
{
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d\n", (LL)fact[a] * infact[a - b] % MOD * infact[b] % MOD);
}

int main()
{
    int T;
    pre();
    scanf("%d", &T);
    while(T --) Work();
    return 0;
}

卢卡斯定理

内容

对于非负整数 a,b 和质数 p 都有：C_a^b\equiv C_{a\bmod p}^{b\bmod p}\times C_{\lfloor a\div p\rfloor}^{\lfloor b\div p\rfloor}\pmod{p}

证明非常麻烦，建议直接记结论，若有需要请自行百度。

或者等我闲下来之后回来更新。

例题

题目描述

给定三个正整数 a,b,p（1\le a,b\le 10^{18}，1\le p\le 10^5），其中 p 是质数，求 C_a^b\bmod p

思路分析

显然不能直接算。

考虑到 p 不大，因此可以直接上卢卡斯定理。

时间复杂度：O(p\log p)

代码

#define LL long long

int qmi(int a, int k, int p)
{
    int ans = 1;
    while(k)
    {
        if(k & 1) ans = (LL)ans * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return ans;
}

int C(int a, int b, int p) // 求组合数
{
    if(b > a) return 0; // 边界条件
    int ans = 1;
    for(int i = 1, j = a; i <= b; i ++, j --) // 因为 a,b 不会超过 p 因此直接对着原始公式爆算即可
    {
        ans = (LL)ans * j % p;
        ans = (LL)ans * qmi(i, p - 2, p) % p; // 为什么要乘逆元你们懂得吧？
    }
    return ans;
}

int lucas(LL a, LL b, int p)
{
    if(a < p && b < p) return C(a, b, p); // 边界条件
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

卡特兰数

定义

对于类似于：可以将长度为 n 的问题分解成长度为 x,n-x（1<x<n）的两个子问题的问题都可以使用卡特兰数求解。

这也就是原始公式：h(n+1)=C_0C_n+C_1C_{n-1}\dots C_nC_0 的由来。

公式

h(n)=\dfrac{C_{2n}^n}{n+1}