定义

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

含义

$a\equiv b\pmod{m}$ 表示 $a\bmod m=b\bmod m$，在 C++ 中可以表示为 a % m == 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}$

对原式进行移项即可

求法

• 当 $p$ 是质数：

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

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

• 否则

扩展欧几里得定理。

说说我对逆元的理解

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

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

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

• 在 $R$ 中，$a\div b$ 可以表示为 $a\times b^{-1}$；（我不知道可不可以这么说）

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

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

所以，共同点：

• 在 $R$ 中，$b\times b^{-1}=1$；
• 在同余系中，$b\times b^{-1}\equiv 1\pmod p$。

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

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

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

定义

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

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

质数的判定——试除法：

$d | n$ 代表的含义是 $n$ 能被 $d$ 整除。（这里的 | 代表整除，在 C++ 中可以表示为 n % d == 0）

一个合数的约数总是成对出现的，如果 $d|n$，那么 $(n\div d)|n$，因此我们判断一个数是否为质数的时候，只需要判断较小的那一个数能否整除 $n$ 就行了，即只需枚举 $d\le(n\div d)$，即 $d\times d\le n$，$d\le \sqrt{n}$ 就行了。

sqrt(n) 这个函数执行的时候比较慢。

代码：

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$ 本身）都是互质。

只有一个质因子的正整数为质数。

代码：

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))$。

代码：

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 的最小质因子。

代码

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;
        }
    }
}

试除法求所有约数

代码

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$ 个。

代码

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$ 的所有约数的和为

代码

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)$；

  证毕。

代码

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}$：

证毕。

代码

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)$。

代码仅仅是在线性筛筛质数的情况下增加了几句话。

先上代码：

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)$。

代码

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)$ 一定是最小正整数和。

  关于存在性证明请见扩展欧几里得算法。

本体

直接上代码：

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$。

一直递归即可求出最终解。

此时返回的 $x,y$ 只是一组解，若要求通解，则令 $t=\frac{b}{\gcd(a,b)}$，则 $x$ 的通解为 $x+kt$，则 $x$ 的最小正整数解即为 $(x\bmod t + t)\bmod t$。

关于裴蜀定理

由以上代码得，一定能返回一组可行解。

因此，裴蜀定理成立。

而对于 $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}$。

一般题目会要求输出最小的正整数解，此时输出 $(x \bmod M + M)\bmod M$ 即可。

证明

暂时不会。

先挖个坑。

定义

$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)$

$fact$ 与 $infact$ 数组可以在线性时间内预处理。

时间复杂度：$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}$