算法

欧几里得算法

证明

第一种方法是根据更相减损 ：

$$\gcd(a,b) = \gcd(a,a-b) = \gcd(b,a-b)$$

更相减损的证明就是 $d \mid a,d \mid b$ 则 $d \mid (a-b)$ ，反之亦然，因此他们的公约数相同，最大公约数相同，得证。

然后根据更相减损每次给 $a$ 减去 $b$ 直到 $a < b$ ,这个过程就等价于 $a$ 对 $b$ 取模。

然后欧几里得算法得证。

第二种方法是 ：

不妨假设 $a > b$ 容易发现 ： 如果 $b \mid a$ ，那么 $b$ 就是两者的最大公约数。

对于不能整除时 ： 我们可以设 $a = kb + r$ ，其中 $r < b$ 。

我们要证明的就是 $\gcd(a,b) = \gcd(b,a \bmod b \; )$。过程如下 ：

因为 $a = kb + r$ ，所以显然有 $r = a \bmod b$ 。

设 $d \mid a,d\mid b$ ，由 $c = a - kb$ 同除 $d$

可得 ： $\frac{r}{d} = \frac{a}{d} - k\frac{b}{d}$。

等号右边显然是整数，因此 $d \mid r$ ,所以任意 $a,b$ 的公约数也是 $a \bmod b$ 的公约数。公约数相同，因此最大公约数也相同。

反过来证明的方法几乎一样 ：

设 $d \mid r,d\mid b$ ，由 $c = a - kb$ 同除 $d$

同样可得 ：

$$\frac{r}{d} + k\frac{b}{d} = \frac{a}{d}$$

式子左侧显然为整数，所以有 $d \mid a$ ,所以充分性和必要性都得证，我们得出命题等价：

$$\gcd(a,b) = \gcd(b,a \bmod b)$$

于是由这个式子我们显然有了实现 ：

实现

namespace way1{
    int gcd(int m,int n)
    {
        int r;
        if (m < n) std :: swap(m,n);
        while(m % n)//辗转相除
        {
            r = m % n;
            m = n;
            n = r;
        }
        return n;
    }
}

namespace way2{
    int gcd(int x,int y)
    {
    	return y ? gcd(y,x % y) : x;
    }
}

namespace way3{
    int gcd(int x, int y)
    {
        while(y ^= x ^= y ^= x %= y);
        return x;
    }
}

(当然可以直接 __gcd )

例题是UVA11426 那就推一下这个例题的式子罢 ：

$$\begin{split} \sum_{i=1}^n \sum_{j = i+1}^n &= \sum_{j = 2}^n \sum_{i = 1}^{j-1} \gcd(i,j)\\ &= \sum_{d=1}^n d \times \sum_{j=2}^n \sum_{i = 1}^{j-1}[\gcd(i,j) = d] \\ &= \sum_{d=1}^n d \times \sum_{j=2}^{\lfloor \frac{n}{d} \rfloor} \sum_{i=1}^{j-1}[i \bot j]\\ &= \sum_{d=1}^n d \times \sum_{j=2}^{\lfloor \frac{n}{d} \rfloor}\varphi(j)\\ \end{split}$$

到这里第一步已经成功了，都是经典操作也没什么难度。考虑进一步优化： 设 $S(x) = \sum_{j=2}^x \varphi(j) ,f(x) = \sum_{j = 1}^x j$.

显然原式变成 ：

$$\sum_{d=1}^n d \times S({\lfloor \frac{n}{d} \rfloor})$$

因为 $\lfloor \frac{n}{d} \rfloor$ 被重复计算多次，显然考虑数论分块。

于是原式化为 ：

$$\sum(f(r) - f(l-1)) \times S(\lfloor \frac{n}{l} \rfloor)$$

预处理 $f(x),S(x)$ 的值，最终对于 $T$ 次询问总的时间复杂度是 $O(n + T \sqrt{n} )$ ,可以通过本题。

扩展欧几里得算法(exgcd)

推导

由裴蜀定理我们已知 ： $ax + by = \gcd(a,b)$ 一定存在整数解。

使用 exgcd 可以得到上述方程的一组特解。

考虑解这个方程，显然当 $b = 0$ 时我们有 : $x = 1,y \in Z$。

当 $b \neq 0$ 时，我们设：

$$\begin{split} &\gcd(a,b) = ax_1 + by_1\\ &\gcd(b,a \bmod b) = bx_2 + (a \bmod b)y_2 = bx_2 + (a - \lfloor \frac{a}{b} \rfloor b)y_2\\ \end{split}$$

两式左边相等，那么拆开括号就有 ：

$$ax_1 + by_1 = ay_2 + b(x_2 - \lfloor \frac{a}{b} \rfloor y_2)$$

两边对应系数得 ：

$$x_1 = y_2,y_1 = x_2 - \lfloor \frac{a}{b} \rfloor y_2$$

成功了！

于是我们就可以像求gcd一样递归求解了

代码实现

按照这个式子写的代码长这样 ：

int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x = 1;y = 0;
        return a;
    }
    int d = exgcd(b,a % b,x,y);
    int t = x;x = y;
    y = t - a/b * y;
    return d;
}

函数的返回值就是顺便求了一下gcd。

或者这样写 ：

void exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
       x = 1;y = 0;
       return;
    }
    exgcd(b,a%b,y,x);
    y -= a/b*x;
}

本质上是完全等价的，而且这个板子更好记一些

之后令 $g = \gcd(a,b)$ 则 $\text{lcm}(a,b) = a * b / g$ 又 $ax + \text{lcm}(a,b) + by - \text{lcm}(a,b) = c$ 所以就有 ：

$$a(x + b/g) + b(y - a/g) = c$$

例题

一个很强的板子是 P5656 。

题意就是 ：

$T(T \le 2e5)$组数据，每组给出 $a,b,c \in [1,10^9]$ ,询问使得 $ax+by = c$ 成立的解。

若有正整数解，输出：

• 正整数解的个数
• 正整数解中最小的 $x$ 和最大的 $y$
• 正整数解中最大的 $x$ 和最小的 $y$

否则，若有整数解，输出 ：

• 所有整数解中 $x$ 的最小正整数值， $y$ 的最小正整数值

否则，输出 $-1$

大概说一下这个题罢，虽然大概所有人都应该会写exgcd，但是能完整解决这道题的我觉得不多（

$$ax + by = c$$

显然，$\gcd(a,b) \mid (ax+by)$ 故 $\gcd(a,b) \nmid c$ 时无解

然后我们就可以由exgcd求出一组整数 $x_0,y_0$ ，使得：

$$ax_0 + by_0 = \gcd(a,b)$$

等号两边同除 $gcd(a,b)$ 后同乘 $c$ ，就是 ：

$$a \frac{x_0c}{\gcd(a,b)}+ b \frac{y_0c}{\gcd(a,b)} = c$$

于是我们找到了原方程的一组整数特解 $x_1,y_1$ ：

$$x_1 = \frac{x_0c}{\gcd(a,b)},y_1 = \frac{y_0c}{\gcd(a,b)}$$

接下来考虑构造通解 ：

对于 $\forall d \in Q$ ，必然有 ：

$$a(x_1 + db) + b(y_1 - da) = c$$

所以对于整数通解只需要保证 $da,db \in Z$ 。

设 $d$ 取到最小的可能的正值（实数）时 $d_x = db,d_y = da$ 那么任意解中这两个变量与 $x_1,y_1$ 的偏差一定分别是 $d_x$ 与 $d_y$ 的倍数。

那么显然最小时 $d_x = \frac{b}{\gcd(a,b)} , d_y = \frac{a}{\gcd(a,b)}$，在 $d = \frac{1}{\gcd(a,b)}$ 时取到。

所以通解就是 ：

$$x = x_1 + sd_x,y = y_1 - sd_y$$

其中 $s \in Z$

而且 $x$ 与 $y$ 取值的变化呈负相关。

显然而重要的 ： $s$ 越大， $x$ 越大， $y$ 越小，反之亦然。

考虑是否有正整数解的判定 ：

限制 $x > 0$ ，则 $x_1 + sd_x > 0 ,s > -\frac{x_1}{d_x}$ 限制 $y > 0$ ，则 $y_1 - sd_y > 0 ,s < \frac{y_1}{d_y}$

所以若要有正整数解，则要满足 ：

$$-\frac{x_1}{d_x} < s < \frac{y_1}{d_y}$$

当这个不等式无解时即无正整数解， $s$ 位于左端点时即为 $x$ 的最小正整数值， $s$ 位于右端点时即为 $y$ 的最小正整数值。

有解时即为有正整数解，正整数解个数就是在这个范围内的 $s$ 的个数，容易求得。

$x$ 的最大值和 $y$ 的最小值都是在 $s$ 的右端点取到，$x$ 的最小值和 $y$ 的最大值都是在 $s$ 的左端点取到。

然后这道题就做完了。

代码的话就长这样 ：

#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
typedef long long ll;

ll a,b,c;
ll exgcd(ll a,ll b,ll &x,ll &y);

void main()
{
    cin >> a >> b >> c;
    ll g = __gcd(a,b);
    if(c % g)
    {
        cout << -1 << '\n';
        return;
    }
    ll x,y;
    exgcd(a,b,x,y);
    x *= c / g,y *= c / g;  //x1,y1
    ll dx = b / g,dy = a / g; // x = x1 + sdx,y = y1 - sdy;
    ll low_s = ceil((-x + 1) * 1.0 / dx);
    ll high_s = floor((y - 1) * 1.0 / dy);
    if(high_s >= low_s)
    {
        ll num = high_s - low_s + 1;
        ll max_x = x + high_s * dx;
        ll min_y = y - high_s * dy;
        ll min_x = x + low_s * dx;
        ll max_y = y - low_s * dy;
        cout << num << ' ' << min_x << ' ' << min_y << ' ' << max_x << ' ' << max_y << '\n';
    }
    else
    {
        ll min_x = x + low_s * dx;
        ll min_y = y - high_s * dy;
        cout << min_x << ' ' << min_y << '\n';
    }
    return;
}

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x = 1,y = 0;
        return a;
    }
    ll g = exgcd(b,a%b,y,x);
    y -= a / b * x;
    return g;
}

}

signed main()
{
    int T;
    std :: ios :: sync_with_stdio(false);
    for(std :: cin >> T;T;T--)
    Pozhu :: main();
    return 0;
}

类欧几里得算法

欧几里得全家桶（bushi

类欧几里得算法用来解决一些计数问题，尤其是可以出现下取整符号的情况。虽然考的比较少但是很好写~~，有时候可以拿来爆标~~。

推式子的过程有些复杂，写过专门的一篇文章，就放一个link罢。

整除分块

也叫数论分块

放一些简单的东西来缓和一下气氛（

通常来讲我们会在以下场合使用整除分块 ：

$$\sum_{i = 1}^n\left \lfloor \frac{n}{i} \right \rfloor$$

推导

大眼观察可以猜出 $\left \lfloor \frac{n}{i} \right \rfloor$ 总是隔一段才变一次（因为是整除）

于是可以考虑以这个变化的位置为分界点进行一个分块，对于每一块我们只进行一次求值，然后乘上块长就可以得到一整块的答案。

假设我们当前的左端点是 $l$ ，右端点是 $r$ ，这个区间内单点的值为 $k$ ，那么就有 ：

$$k = \left \lfloor \frac{n}{l} \right \rfloor = \left \lfloor \frac{n}{r} \right \rfloor$$

对于 $i \in [l,r]$ ，显然 $r$ 是所有 $i$ 中的最大取值。因为 $i \ast k \le n, i \le \frac{n}{k}$ 所以有 ：

$$r = \left \lfloor \frac{n}{k} \right \rfloor = \left \lfloor \frac{n}{\left \lfloor \frac{n}{l} \right \rfloor} \right \rfloor$$

其复杂度是 $O(\sqrt{n})$ ，证明会在下面给出

代码实现

for(int l = 1,r;l <= n;l = r + 1)
{
    r = n / (n / l);
    ans = ans + (r - l + 1) * (n / l);
}

要注意到整除分块的适用范围很广，以上模板仅是对于最平凡的场合，而整除分块常见于杜教筛和莫反当中，在相应文章中可以看到整除分块的频繁出现。

复杂度证明

这里给出整除分块的复杂度证明。

对于 ：

$$\sum_{i = 1}^n\left \lfloor \frac{n}{i} \right \rfloor$$

我们把 $i$ 的取值范围分为两部分进行讨论。

第一部分 ： $1 \le i \le \sqrt{n}$ ，容易发现这样的 $i$ 最多只有 $\sqrt{n}$ 个，考虑最坏情况，每个 $\left \lfloor \frac{n}{i} \right \rfloor$ 的取值都不同，此时块长为 $1$ ，最多有 $\sqrt{n}$ 块。

第二部分 ： $\sqrt{n} < i \le n$，容易得到 $\left \lfloor \frac{n}{i} \right \rfloor < \sqrt{n}$ ，这样的取值最多有 $(\sqrt{n} - 1)$ 个，意味着最多有 $(\sqrt{n}-1)$ 块。

于是块数最多为 $2 \sqrt{n} - 1$ ，我们对于每块内求解的复杂度为 $O(1)$ ，于是总复杂度为 $O(\sqrt{n})$ ，得证。

例题

首先是模板题：H(n)

如果有一道题目是专门考察整除分块的，那么你一定很难看出来这是整除分块（

P2261 [CQOI2007]余数求和

给定 $n,k$ ,$n,k \le 10^9$，求 ：

$$\sum_{i = 1}^n k \bmod i$$

考虑模的意义是整除取余，于是有 ：

$$ans = \sum_{i = 1}^n (k - i \lfloor \frac{k}{i} \rfloor)$$

于是做完了，剩下的应该不用说了。

P3935 Calculating

进行一个没有难度的转化题意，发现是求 $l \sim r$ 的因数个数之和。复杂度要求至多为根号级别。

考虑一个经典套路，于是我们把题意简化为求 $1 \sim n$ 的因数个数之和。

那么考虑计算每一个数的贡献再合并，于是变成了枚举每个因数，统计它的倍数个数再求和。

关于这为什么就是答案，一个简单明了的解释是一个推导过程 :

$$\begin{split} f(x) &= \sum_{i = 1}^x[i \mid x]\\ \end{split}$$

于是答案就是 ：

$$\sum_{x = 1} ^ n \sum_{i = 1}^x[i \mid x] = \sum_{i = 1} ^ n \lfloor \frac{n}{i} \rfloor$$

最后一步转化是考虑 $i$ 对于每一个倍数都产生 $1$ 的贡献，于是 $i$ 的贡献就是其倍数个数。

然后上一个整除分块，这题做完了。

Cipolla 算法

用来解决形如

$$x^2 \equiv n \mod p$$

的问题（模意义开根）。其中 $p$ 为奇素数。

这部分参考Kewth 的博客，具体而言，文章架构和讲述顺序大体一致。

那是一篇优秀的博客，我从那里学会了二次剩余。他大概比我讲的清楚些

解的数量

数学直觉告诉我们解可能不唯一，注意我们讨论的范围是 $[0,p)$。

考虑两个不同解 $x_1,x_2$，代入原式易得 $x_1^2 \equiv x_2^2$,于是移项使用平方差公式，有 ：$(x_1 + x_2)(x_1 - x_2) \equiv 0$。

由于他们是不同解，有 $x_1 + x_2 \equiv 0$，于是这两数为模意义下相反数，发现只有两个解。考虑是否有特殊情况，发现当一个解为 $0$ 时只有一解。而剩余情况下，因为模数是奇素数，两数奇偶性不同，两数不可能相同。

这里涉及到一个二次剩余的概念，注意二次剩余是一种数，这个意义建立在一个模数下。对于一个模数 $p$，一个非 $0$ 整数 $n$，如果 $x^2 \equiv n \mod p$ 存在整数解，那么 $n$ 是一个二次剩余，否则不是。

同时可以发现每一对相反数都对应一个二次剩余，且这些二次剩余两两不同（若相同则有四个解显然不成立）。于是二次剩余的数量是 $\frac{p-1}{2}$，剩下的数都是非二次剩余，数量相同。

欧拉准则

用来判定一个数是否为二次剩余。

不妨认为 $n$ 的范围是 $[0,p)$。

特殊判定 $n=0$ 的情况，它不是二次剩余，它模意义下的根只有一个，是它本身。

判定要用的内容是 ：

如果 $n$ 是二次剩余，当且仅当 $n^{(\frac{p-1}{2})} \equiv 1$，否则 $n$ 是非二次剩余，且$n^{(\frac{p-1}{2})} \equiv -1$。

下面是一个证明 ：

若 $n ^ {(\frac{p-1}{2})} \equiv 1$，那么将 $n$ 表示为 $g^k$，其中 $g$ 是模 $p$ 意义下的原根。

那么 $g^{k \frac{p-1}{2}} \equiv 1$。由于 $g$ 是原根，有 $p-1 \mid k \frac{p-1}{2}$，这是阶的性质，可见阶与原根中对于阶性质的介绍。

于是 $k$ 一定是偶数，那么 $x = g^{\frac{k}{2}}$ 即为所求解。

我们通过构造可行解的方法证明了此时的 $n$ 是二次剩余。

由费马小定理得到 $n^{p-1} \equiv 1$，由于 $p$ 是奇素数，$p-1$一定是偶数，于是化为 $n^{2(\frac{p-1}{2})} \equiv 1$。那么 $n^{(\frac{p-1}{2})}$ 是 $1$ 开根的解，于是 $n^{(\frac{p-1}{2})}$ 的值只能是 $1$ 或 $-1$。

如果 $n$ 是二次剩余，那么 $x^2 \equiv n$ 有整数解，那么就有 $x^{p-1} \equiv 1$。

于是我们证明了对于任意一个二次剩余 $n$ 都有上式成立。

于是我们证明了充分性和必要性，得到 $n$ 是二次剩余等价于$n^{(\frac{p-1}{2})} \equiv 1$。

实际上有个东西叫勒让德符号，但是与上面的判定方法本质相同，现在的介绍足以解决这一问题，就不再引入新的概念。

那么有了这个引理之后，我们应该如何求解原问题呢？

Cipolla

找到一个 $a$ 满足 $a^2 - n$ 是非二次剩余。非二次剩余的数量大致占一半，于是期望两次可以找到一个合法的 $a$，这是一个小常数。

然后定义 $i^2 \equiv a^2 -n$，这并不是二次剩余，于是像是对负数开根那样，我们的 $i$ 是一个“虚数”，于是可以把所有数表示成 $a + bi$ 的形式，其中 $a,b \in [0,p)$。

结论是 $(a+i) ^ {p + 1} \equiv n$。

证明 ：

引理1

$$i^p \equiv -i$$

证明 ：

$$i^p \equiv i (i^2) ^ {\frac{p-1}{2}} \equiv i (a^2 - n) ^ {\frac{p-1}{2}} \equiv -i$$

得证。

引理2

$$(A + B) ^ p \equiv A^p + B^p$$

证明类似 Lucas 定理的证明中对于引理二的证明，用二项式定理展开即可，不再赘述。

有了这两个引理之后我们可以考虑去证明上述结论 ：

$$(a+i) ^ {p+1} \equiv (a^p + i^p)(a + i) \equiv (a-i)(a+i) \equiv a^2 - i^2 \equiv n$$

于是得证。

于是 $(a+i) ^ {\frac{p+1}{2}}$ 就是一个解，其相反数是另一个解。

但是这是虚数运算，大家当然会产生疑问 ： 这个结果的虚部一定为 $0$ 吗？

答案是肯定的。用反证法可以得到这个结论：

假设有 $(A + Bi) ^ 2 \equiv n$ 且 $B \neq 0$。

注意为什么我们设这样的形式，原因当然是方便讨论。注意上边的解一定可以找到一个这种形式的叙述表示。

于是 $A^2 + B^2i^2 + 2 ABi \equiv n$,移项得到 $A^2 + B^2(a^2 - n) - n \equiv -2ABi$

这里可以运用等式的基本性质，等号左边没有虚部，那么右边的虚部也一定为 $0$。

即 $AB = 0$，已知 $B \neq 0$，那么 $A = 0$

于是化简式子 ：

$$B^2(a^2 - n) \equiv n$$

也就是 :

$$i^2 \equiv n B^{-2}$$

$B^{-2}$是一个二次剩余，因为显然有一解为 $B^{-1}$。

$n$ 也是二次剩余，那么 $nB^{-2}$ 显然也是二次剩余，解是原解的乘积。

这与 $i^2$ 是非二次剩余矛盾，就像是虚数的 $i^2 > 0$ 一样离谱。

于是我们得到了矛盾，证明了假设不成立，即不存在那样的 $B$，我们求出的解虚部一定为 $0$。

那么我们就可以解决开头提出的问题了。

这是板子题 ： P5491 【模板】二次剩余。

BSGS算法

BSGS(baby-step giant-step) ,即大步小步算法，常用于求解离散对数问题。也就是说，该算法可以在 $O(\sqrt{p})$ 的时间内求解

$$a^x \equiv b \; (\bmod p \; )$$

普通的BSGS算法要求 $a \bot p$ ，不要求 $p$ 是素数。

令 $x = A \lceil \sqrt{p} \rceil - B$ ，其中 $0 \le A,B \le \lceil \sqrt{p} \rceil$ ,则有 $a^{A \lceil \sqrt{p} \rceil - B} \equiv b \; (\bmod p \;)$ ,两边同乘 $a^B$ ，那么我们得到 ：

$$a^{A \lceil \sqrt{p} \rceil} \equiv b \cdot a^B \; (\bmod p \; )$$

因为我们已知 $a,b$ ，于是我们可以枚举 $B$ ，预处理出所有 $ba^B$ 的取值，使用 map 或 hash 建立起相应的映射，然后逐一计算 $a^{A \lceil \sqrt{p} \rceil}$ ，也就是枚举 $A$ ，检查是否有与之对应的 $ba^B$ ，从而我们可以得到所有的 $x$ ，$x = A \lceil \sqrt{p} \rceil - B$

显然由 $A,B \le \sqrt{p}$ ,上述算法的时间复杂度为 $\Theta(\sqrt{p})$ ，若使用 map 则多一个 $\log$ 。

要求 $a \bot p$ 的原因 ：

我们求得的是 $A,B$ ，而要通过 $A,B$ 的值推出 $x$ 的值需要 $a^{A\lceil \sqrt{p} \rceil } \equiv ba^B \Leftrightarrow a^{A\lceil \sqrt{p} \rceil-B} \equiv b \; (\bmod p \;)$，即这个同余式对于两边同除 $a^B$ 仍成立。

所以必须要有 $a^B \bot p$ ,也就是 $a \bot p$ 。

模板题是P3846，代码如下 ：

#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
typedef long long ll;
ll a,x,n,p;

ll ksm(ll ,ll );
ll BSGS(ll ,ll ,ll );

void main()
{
    scanf("%lld%lld%lld",&p,&a,&n);
    ll ans = BSGS(a,n,p);
    if(ans == -1)
        puts("no solution");
    else
        printf("%lld",ans);
    return;
}

ll BSGS(ll a,ll b,ll p)
{
    b %= p;
    map<ll ,ll > has;has.clear();
    ll t = sqrt(p) + 1;
    for(ll j = 0,tmp = b;j<t;tmp = tmp * a % p,j++)
    has[tmp] = j;
    a = ksm(a,t);
    if(!a) return b == 0 ? 0 : -1;
    for(ll i = 1,tmp = a;i<=t;tmp = tmp * a % p,i++)
    if(has.count(tmp))
    return i * t - has[tmp];
    return -1;
}

ll ksm(ll a,ll b)
{
    ll ans = 1;
    for(;b;b>>=1,a = a * a % p) if(b & 1) ans = ans * a % p;
    return ans;
}

}

signed main()
{
    Pozhu :: main();
    return 0;
}

BSGS算法给我们带来的教益不仅是解决了这个问题，还有其根号分治的思想。

灵活运用类似的思想，我们就可以解决这道题： Maximum Sine

提示：转化题意，考虑类似的分块思路。

放一个题解，使这题有头有尾。

扩展BSGS

扩展BSGS依然用来解决这个问题 ：

$$a^x \equiv b \;(\bmod p \;)$$

但是其中 $a,p$ 不一定互质。

当 $a \bot p$ 时，在模 $p$ 意义下 $a$ 存在逆元，因此可以使用BSGS算法求解（同除 $a^B$ 即同乘 $a$ 的逆元的 $B$ 次方，可行）。 于是我们想办法让他们变的互质。

我们设 $d_1 = \gcd(a,p)$ ，如果 $d_1 \nmid b$ ，则原方程无解。否则我们把方程和模数同时除以 $d_1$ ，得到 ：

$$\frac{a}{d_1}\cdot a^{x-1} \equiv \frac{b}{d_1} \;(\bmod \frac{p}{d_1} \; )$$

如果此时 $a$ 和 $\frac{p}{d_1}$ 仍不互质就再除，设 $d_2 = \gcd(a,\frac{p}{d_1})$ 。如果 $d_2 \nmid \frac{b}{d_1}$ ，则原方程无解，否则同时除以 $d_2$ 得到 ：

$$\frac{a^2}{d_1d_2}\cdot a^{x-2} \equiv \frac{b}{d_1d_2} \;(\bmod \frac{p}{d_1d_2} \; )$$

不停地这样做下去，直到 $a \bot \frac{p}{d_1d_2\cdots d_k}$。

记 $D = \prod_id_i$ ，那么原方程就是 ：

$$\frac{a^k}{D} \cdot a^{x-k} \equiv \frac{b}{D} \; (\bmod \frac{p}{D} \; )$$

由 $a \bot \frac{p}{D}$ 可得 $\frac{a^k}{D} \bot \frac{p}{D}$ ，这样 $\frac{a^k}{D}$ 就有逆元了，方程两边同乘它的逆元，问题就转化为一个普通的BSGS问题，解出 $x-k$ 的值之后再加上 $k$ 就是要求的解。

但是可能会出现 $x \le k$ 的情况，我们可以在知道 $k$ 之后直接进行 $k$ 次枚举验证答案来避免这种情况对求解造成影响。

模板题是 P4195 ，代码很不优美就不放了。

BSGS解高次剩余

求解

$$x^a \equiv b \;(\bmod p \; )$$

其中 $p$ 为质数。

该模型可以通过一系列转化变为BSGS的基本形式。

前置知识是阶和原根。

由于式子中的 $p$ 为质数，那么一定存在原根 $g$ ，因此对于模 $p$ 意义下任意的数 $x(0 \le x \le p)$ 有且仅有一个数 $i$ 满足 $x = g^i$

Pollard Rho 算法

Fermat 素性测试

Miller-Rabin 素性测试

---

定理

算数基本定理（唯一分解定理）

任意不是质数的正整数 $a$ 能唯一分解为有限个质数幂的乘积 ：

$$a = \prod_{1 \le i \le m} p_i^{c_i}$$

约数个数定理

“小学奥数”

内容

对于一个大于 $1$ 的正整数 $n$ 可以分解质因数 :

$$n = \prod_{i = 1}^k p_i^{a_i} = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k ^ {a_k}$$

则 $n$ 的正约数个数就是 ：

$$\tau(n) = \prod_{i = 1}^k (a_i + 1) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$$

证明

对于上述唯一分解的结果观察 ：

$p_1^{a_1}$ 的约数有 ： $p_1^0,p_1^1 \cdots p_1^{a_1}$ 共 $(a_1 + 1)$ 个，其他质因子同理。

于是总的因子个数可以由乘法原理得到 ：

$$\tau(n) = \prod_{i = 1}^k (a_i + 1) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$$

得证。

例题可以是 欧拉计划 T12 ，答案易求，这里不放了。

裴蜀定理

（又称贝祖定理）

对于任意不全为零的整数 $a,b$ 都 $\exists x,y \in Z$ ，使得 $ax+by = \gcd(a,b)$。

对于不定方程 $ax + by = m$ ，其有解的充要条件是 $\gcd(a,b) \mid m$

证明

充分性

即证明 ： $\gcd(a,b) \mid m$ ，则 $ax+by=m$ 有整数解

假设我们已知 $ax+by = \gcd(a,b)$ 有一组整数解 $x_0,y_0$ 那么显然 $ax+by = m$ 存在一组整数解 $x_1 = x_0 \frac{m}{\gcd(a,b)} ,y_1 = y_0 \frac{m}{\gcd(a,b)}$ ，于是只需证明 $ax+by = \gcd(a,b)$ 一定存在整数解。

然后就可以从网上随便找一篇证明贺一下了

因为大家写的都是一样的而且都没有出处，我也不知道这个证明最先是在哪给出来的qwq，但是有些人写出锅的地方我还是能浅修一下。

设 $d = \gcd(a,b)$，显然有 $d \mid a,d \mid b,d \mid ax+by$

设 $s$ 是 $ax+by$ 的最小正数值，设 $q = \lfloor \frac {a}{s} \rfloor$

于是我们有 $r = a \bmod s = a - qs = a - q(ax+by) = a(1-qx) + b(-qy)$

所以 $r$ 也是 $ax+by$ 的一个取值，并且由取模的来源我们已知 $0 \le r < s$，不难得到 $r = 0$ ，于是由此我们得到 $s \mid a$ ，同理可得 $s \mid b$ ，于是 $s \mid \gcd(a,b)$,即 $s \mid d$

又因为 $d \mid \forall ax+by$ ，而 $s$ 是 $ax+by$ 的一个取值，所以 $d \mid s$

于是证得 $s = d$ (这里已经直接证明了下边的推论三)

于是因为 $s$ 是 $ax+by$ 的一个取值，$d$ 是 $ax+by$ 的一个取值。

换言之 $ax+by = \gcd(a,b)$ 一定存在整数解。

于是我们证明了这一结论。

必要性

即证明 ： $ax + by = m$ 有解，必定有 $gcd(a,b) \mid m$ （比较显然）

$$\gcd(a,b) \mid a$$ $$\gcd(a,b) \mid b$$

所以 $\gcd(a,b) \mid m = ax+by$

应用

zh_dou : 用来做题

可以用来证明奇奇怪怪的东西和推式子 信息上对于这东西常见的套路是枚举gcd 如： 给你T组数据，求 $\sum_{i = 1}^n \sum_{j = 1}^m \gcd(i,j)$ 其中有一步是标准的枚举gcd（经典枚举gcd）

$$\begin{split} & \sum_{i = 1}^n \sum_{j = 1}^m \gcd(i,j)\\ = & \sum_{i = 1}^n \sum_{j = 1}^m \sum_{d \mid i,j} d [\gcd( \frac{i}{d} , \frac{j}{d}) = 1] \end{split}$$

一些推论

一、$a$,$b$可以组成所有 $\gcd(a,b)$ 的倍数(其实是定理的直接结论，等式的基本性质)

二、 $a\bot b \Longleftrightarrow \exists x,y \in Z, ax+by=1$

三、 $ax+by$ 的最小正整数取值为 $\gcd(a,b)$

四、 对于不定方程 $x_1y_1 + x_2y_2 + \cdots + x_ny_n = k,y_i \in Z$ ，其有解的充要条件为 $\gcd({x_i}) \mid k$

五、我们考察不定方程 $ax+by = n$ ,其中 $a \bot b$ 若这个方程有一组解使得 $x \ge 0,y \ge 0$ ，那么称 $n$ 可以被 $a,b$ 表示。

那么 ：

对于互质的 $a,b$ ,记 $C = ab-a-b$ 。由 $a$ 与 $b$ 互质， $C$ 必然为奇数。则有结论 ： 对任意的整数 $n$ ，$n$ 与 $C-n$ 中有且仅有一个可以被表示

(对称性)

所以对称性总结一下就是 ：

可表示的数与不可表示的数在区间 $[0,C]$ 对称（关于 $C$ 的一半对称）。$0$ 可被表示，$C$ 不可被表示；负数不可被表示，大于 $C$ 的数可被表示。

证明 ：

由于 $a \bot b$ ，原方程有整数解（$\gcd(a,b) = 1,ax + by = n \times \gcd(a,b)$） 。 设一组特解为 $x= x_0,y = y_0$ 则通解为：

$$\left\{\begin{matrix} x = x_0 + bt \\ y = y_0 - at \end{matrix}\right.$$

其中 $t \in Z$ 。不难发现我们可以通过调整 $t$ 的取值使得 $y \in [0,a-1]$ ，这只需要在 $y_0$ 上加减若干个 $a$ 。此时我们的 $y$ 已经满足条件了。

第一步 ： 首先我们证明大于 $C$ 的数都可以被表示。当 $n$ 大于 $C$ 时：

$$ax = n-by > ab-a-b-by \ge ab-a-b-b(a-1) = -a$$

也就是说:

$$ax > -a,x > -1$$

因为 $x$ 为整数,所以得到 $x$ 为非负整数， $n$ 可以被表示。

第二步 ： 证明 $C$ 不可被表示，进而 $n$ 与 $C-n$ 不可能都被表示。 考虑反证法。

设 $C$ 可以被表示，也就是说 $ax+by = ab-a-b$ 有非负整数解 $x,y$ 。则 ：

$$ab = a(x+1) + b(y+1)$$

一个我并不喜欢的版本：

因为 $a \bot b$ ，要使等式成立，显然有 ：

$$a \le y+1,b \le x+1$$

(实际上大概连等号都挂不上罢)

而 $a \bot b$ ，且等号右边可以合并同类项，所以我们有 ：

$$a \mid (y + 1),b \mid (x + 1)$$

显然上式化为 ：

$$ab = a(x + 1) + b(y + 1) \ge ab + ab = 2ab$$

而 $ab$ 显然不为0，矛盾。因此证得 $C$ 不可能被表示。

（显然并不显然）

显然当 $y$ 取值最小的时候对应的 $x$ 取值最大

且由上述证明可知存在最小的 $y \in [0,a-1]$

那么下式取 $y \in [0,a-1]$ ，可以得到最大的 $x$

$$a(x + 1) = ab - b(y + 1) = b(a - y - 1) \le 0$$

$a > 0$ 则 $x \le -1$ ，不成立，则 $C$ 不可以被表示，故得证。

因为 $y$ 取最大值

此时若 $n$ 与 $C-n$ 都能被表示，则 $n$ 也能被表示，矛盾。因此我们得到 $n$ 与 $C - n$ 不可能都被表示。

所以第二步完成了

第三步 ： 证明如果 $n$ 不可以被表示，则 $C-n$ 一定能被表示 (即 $n$ 和 $C-n$ 一定有一个能被表示)

由上可知 ： 若 $n$ 不可能被表示，因为我们已经保证了有合法的 $y$ ，那么此时一定有 $x < 0$ 。所以：

$$C - n = ab-a-b-ax-by = a(-x-1) + b(a-1-y)$$

所以 $-X-1$ 和 $a-1-y$ 均为非负，则 $C-n$ 可以被表示。

所以我们证明了对称性

费马小定理

若 $p$ 为素数， $gcd(a,p) = 1$ ， 则 $a^{p-1} \equiv 1 \space (\bmod p \;)$。 另一个等价的形式是 ： 对于任意整数 $a$ ，有 $a^p \equiv a \space (\bmod p \; )$。

证明

设一个质数 $p$ ，我们取一个不为 $p$ 倍数的数 $a$。 构造一个序列 ： $A = {1,2,3,\cdots,p-1}$，显然这个序列有这样一个性质 ：

$$\prod_{i=1}^nA_i \equiv \prod_{i = 1}^n (A_i \times a )\space ( \bmod p\; )$$

对性质的证明 ：

$$\because (A_i,p) = 1$$ $$\therefore (A_i \times a,p) = 1$$

又因为每个 $(A_i \times a )\space ( \bmod p \;)$ 都不同，且 $(A_i \times a )\space ( \bmod p \;) < p$于是每一个 $A_i \times a$ 都对应了一个 $A_i$ 所以 $(A_i \times a )\space ( \bmod p \;)$ 的取值取遍了 $[1,p-1]$ 设 $f = (p-1)!$ ，则 $f \equiv a \times A_1 \times a \times A_2 \times \cdots \times a \times A_{p-1} ( \bmod p \;)$

$$a^{p-1} \times f \equiv f ( \bmod p \;)$$

所以

$$a^{p-1} \equiv 1 ( \bmod p \;)$$

故得证。我认为这个证明方法是最简单的一种。

另外的证明方法是由于 $m$ 为质数，对于欧拉定理代入 $\varphi(m) = m-1$ 即可得到费马小定理。

euler定理

译名 ： 欧拉定理

内容

若 $\gcd(a,m) = 1$，则 $a^{\varphi(m)} \equiv 1 (\bmod m)$。

证明

构造一个模 $m$ 意义下的简化剩余系 $r_1,r_2,\dots,r_{\varphi(m)}$，由于 $a \bot m$，不难得到 $ar_1,ar_2,\dots,ar_{\varphi(m)}$ 同样为模 $m$ 意义下的简化剩余系。

于是有乘积相等（简系的元素相同）： $r_1 \cdot r_2 \cdot \dots \cdot r_{\varphi(m)} \equiv ar_1 \cdot ar_2 \cdot \dots \cdot ar_{\varphi(m)} \equiv a^{\varphi(m)} \cdot r_1 \cdot r_2 \cdot \dots \cdot r_{\varphi(m)}$

那么两边消去简系之积得到：

$$a^{\varphi(m)} \equiv 1 (\bmod m)$$

于是欧拉定理得证。

欧拉定理本身的应用较少，更多被应用的是扩展欧拉定理。

那么下面我们来介绍扩展欧拉定理的内容。

扩展euler定理

内容

$$a^b \equiv \begin{cases} a^{b \bmod \varphi(m)} & \gcd(a,m) = 1\\ a^b & \gcd(a,m) \neq 1,b < \varphi(m)\\ a^{(b \bmod \varphi(m)) + \varphi(m)} & \gcd(a,m) \neq 1,b \ge \varphi(m) \end{cases} (\bmod m)$$

第二行表示此时不能降幂，对于一般问题下的 $m$，此时的范围已经足够小，我们可以接受直接求解的复杂度。

实际上扩展欧拉定理的形式优美，易于记忆，即使不了解证明，在很大程度上应用也不会受到限制。

倘若想要了解详细的证明过程，可以参考 oi-wiki 中的内容（尽管这里也是引用的证明）。

受到一些限制，这里暂不展开描述扩展欧拉定理的证明。

放一下模板题：P5091 【模板】扩展欧拉定理

然后可以尝试做一下这题：P4139 上帝与集合的正确用法

wilson定理及扩展

译名 ： 威尔逊定理

内容

对于素数 $p$ 有 ：

$$(p-1)! \equiv -1 (\bmod p \;)$$

证明

oi-wiki上的证明看起来很严谨，这里随便给出一个证明 ：

$2 \sim p-2$ 的数在模 $p$ 意义下都有唯一逆元，且不是本身，于是它和逆元配对消掉，剩下的只有 $1$ 和 $p-1$ ，$1$ 没有贡献， $p-1 \equiv -1$,于是定理得证。

二项式定理

内容

二项式定理表明了二项式幂次展开后的各项系数：

$$(a+b)^n = \sum_{i = 0}^n \binom{n}{i}a^{n-i}b^i$$

证明

当 $n = 1$ 时，结论显然成立。

当结论对于 $n - 1$ 成立时：

$$\begin{split} (a+b)^n &= (a+b)^{n-1} * (a+b)\\ &= \left ( \sum_{i = 0}^{n-1} \binom{n-1}{i} a^{n-i-1} b^i \right ) (a+b)\\ &= \sum_{i = 0}^{n-1} \binom{n-1}{i} a^{n-i} b^i + \sum_{i = 0}^{n-1} \binom{n-1}{i} a^{n-i-1} b^{i+1}\\ &= \sum_{i = 0}^{n-1} \binom{n-1}{i} a^{n-i} b^i + \sum_{i = 1}^{n} \binom{n-1}{i-1} a^{n-i} b^{i}\\ &= \binom{n-1}{0} a^nb^0 + \sum_{i = 1}^{n-1} \binom{n}{i} a^{n-i}b^i + \binom{n-1}{n-1}a^0 b^n \end{split}$$

其中用到了 $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$ 的结论。

易得 :

$$\binom{n-1}{0} a^nb^0 = \binom{n}{0}a^nb^0$$ $$\binom{n-1}{n-1}a^0 b^n = \binom{n}{n}a^0b^n$$

于是我们有：

$$(a+b)^n = \sum_{i = 0}^n \binom{n}{i} a^{n-i}b^i$$

于是此时结论对 $n$ 也成立。

由数学归纳法证得结论成立。

广义二项式定理

牛顿还将二项式定理推广到了幂为一般实数的情形。

内容

$$(x + y) ^ a = \sum_{k = 0}^{+\infty} \binom{a}{k}x^{a-k}y^k$$

其中 $a$ 可以取任意实数， $\binom{a}{0} = 1$。

中国剩余定理

中国剩余定理又称孙子定理，英文简写为CRT。

主要作用是求解线性同余方程组（也叫模线性方程组）。

像这样 ：

$$\left\{\begin{matrix} x \equiv a_1 \;( \bmod n_1 \;) \\ x \equiv a_2 \;( \bmod n_2 \;) \\ \vdots\\ x \equiv a_k \;( \bmod n_k \;) \\ \end{matrix}\right.$$

普通的CRT要求模数之间两两互质。

流程

1. 计算所有模数的乘积 $N$
2. 对于第 $i$ 个方程 ：a. 计算 $m_i = \frac{N}{n_i}$b. 计算 $m_i$ 在模 $n_i$ 意义下的逆元 $m_i^{-1}$c. 计算 $c_i = m_im_i^{-1}$ 对 $N$ 取模
3. 方程组模 $N$ 意义下的唯一解为 ： $x = \sum_{i=1}^{k} a_ic_i$

模板题是 P1495

代码如下 ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,r[20] , a[20], N = 1,ans;
void exgcd(ll a, ll b, ll &x, ll & y){
    if(!b){
        x = 1;
        y = 0;
        return;
    }
    exgcd(b,a%b,x,y);
    ll t = x;
    x = y;
    y = t- (a/b) * y;
}
int main()
{
    cin>>n;
    for(int i= 1;i<=n;i++)
    scanf("%lld%lld",&r[i],&a[i]),N *= r[i];
    for(int i = 1;i<=n;i++)
    {
        ll m = N / r[i],b,y;
        exgcd(m,r[i],b,y);
        if(b < 0) b += r[i];
        ans = (ans + a[i] * m * b);
    }
    cout<<ans%N;
}

（注意代码中输入的第一个数是模数，第二个数是余数。）

证明

要证明CRT的正确性，我们只需要证明通过上述过程算出来的 $x$ 满足每一个同余方程。

对于不相等的 $i$ 和 $j$ ，我们显然有 $n_i \mid m_j$ ，即 $m_j \equiv 0 \;(\bmod n_i \;)$ 。

于是 ： $c_j \equiv m_j \equiv 0 \;(\bmod n_i \;)$ 。

又有 ： $c_i \equiv m_i \cdot (m_i^{-1} \; \text{mod} \; n_i) \equiv 1 \;(\bmod n_i \;)$

所以我们可以得到 ：

$$\begin{aligned} x & \equiv \sum_{j=1}^{k} a_{j} c_{j} & &\left(\bmod n_{i} \; \right) \\ & \equiv a_{i} c_{i} & &\left(\bmod n_{i} \; \right ) \\ & \equiv a_{i} \cdot m_{i} \cdot\left(m_{i}^{-1} \bmod n_{i} \; \right ) & &\left(\bmod n_{i} \; \right) \\ & \equiv a_{i} & &\left(\bmod n_{i} \; \right) \end{aligned}$$

于是当 $i$ 取遍 $1 \sim k$ 时，我们求得的 $x$ 都是对应方程的合法解，于是我们证明了这个算法的正确性。

我们对输入的 $a_i$ 没有特殊限制，因此对于任何一组输入的 ${a_i}$ 都对应一个解 $x$ 。

若 $x \neq y$ ，则总存在一个 $i$ 使得 $x$ 和 $y$ 在模 $n_i$ 下不同余。

扩展中国剩余定理

扩展中国剩余定理的简写为 EXCRT ,用来处理 CRT 中模数不互质的情况。

推荐一手 阮行止的博客 ，写的很详细。

设两个方程分别为 ：

$$x \equiv a_1 (\bmod m_1 \; )$$ $$x \equiv a_2 (\bmod m_2 \; )$$

我们把同余方程转化成不定方程 ：

$$x = m_1k_1 + a1 = m_2k_2 + a_2 \;\; k_1,k_2 \in Z$$

于是有 :

$$m_1k_1 - m_2k_2 = a_2 - a_1$$

由裴蜀定理可得 ： 当 $a_2 - a_1$ 不能被 $\gcd(m1,m2)$ 整除时，方程无解。

其他情况下，我们可以使用 $exgcd$ 求出一组可行解 $(k_1,k_2)$ ，具体流程如下 ：

设 $d = \gcd(m_1,m_2)$ , $p_1 = \frac{m_1}{d}$ , $p_2 = \frac{m_2}{d}$ ,于是上式等价于 ：

$$k_1p_1 - k_2p_2 = \frac{a_2 - a_1}{d}$$

等号右边是整数。

$$x_0 p_1 + y_0 p_2 = 1$$

假设我们求得了这个方程的一组解 $(x_0,y_0)$，那么我们就显然求出了 $k_1,k_2$ ：

$$k_1 = \frac{a_2 - a_1}{d}x_0,k_2 = - \frac{a_2 - a_1}{d}y_0$$

于是 ：

$$x = a_1 + k_1 m_1 = a_1 + \frac{a_2 - a_1}{d}x_0m_1$$

于是我们构造出了一个符合条件的解，下面我们考虑构造出整个解系 ：

我们有定理 ：

若有特解 $x'$ ，那么上述两个线性同余方程构成的同余方程组的通解是 ： $x'+k\cdot \text{lcm}(m_1,m_2)$，也就是 ：

$$x \equiv x' (\bmod \text{lcm}(m_1,m_2))$$

这个通解的正确性是显然的，然而我们需要考虑的问题是它是否全面，即为何一个 $\text{lcm}(m_1,m_2)$ 当中只会有一个解的问题。

为了解决这个唯一性问题，我们通常采取反证法 ： 假设 $x,y$ 都是满足条件的解，然后证明 $x = y$ ，那么就可以证明唯一性。

设上述问题中存在 $0 \le x,y \le \text{lcm}(m_1,m_2)$ ，都使得原同余方程组成立。

不妨设 $x \ge y$ ,那么立即可以发现 ：

$$x - y \equiv 0 (\bmod m_1 \; )$$ $$x - y \equiv 0 (\bmod m_2 \; )$$

也就是 ：

$$\text{lcm}(m_1,m_2) \mid (x-y)$$

因为 $x,y$ 都是小于 $\text{lcm}(m_1,m_2)$ 的数，他们作差也一定小于 $\text{lcm}(m_1,m_2)$ ，又有整除，于是 $x - y = 0,x = y$ ,得证。

则原来两个方程组成的方程组的解为 $x \equiv b (\bmod M)$ ，其中 $b = m_1k_1 + a_1$ , $M = \text{lcm}(m_1,m_2)$

对于有多个方程的情况，我们使用相同的方法对它进行两两合并，就可以解出同余方程组了。

模板题是P4777

代码如下 ：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6;
int n,x,y,A,B,C;
int m[maxn],a[maxn],ans;

int qmul(int a,int b,int mo){
    int ans = 0,base = a;
    while(b){
        if(b&1) ans = (ans+base) %mo;
        base = (base+base) %mo;
        b >>= 1;
    }
    return ans;
}

int exgcd(int a,int b,int &x,int &y) {
    if(!b) {
        x=1, y=0;
        return a;
    }
    int g = exgcd(b,a%b,x,y);
    int tx = x;
    x = y;
    y = tx-(a/b)*y;
    return g;
}
signed main()
{
    scanf("%lld",&n);
    for(int i = 1; i <= n; i++)
    scanf("%lld%lld",&m[i],&a[i]);
    for(int i = 2; i <= n; i++) {
        A = m[1], B = m[i], C = a[i]-a[1];
        C = (C%B+B)%B;
        int g = exgcd(A,B,x,y);
        x = qmul(x,(C/g),B);
        x = (x%B+B)%B;
        a[1] = a[1]+ qmul(m[1],x,m[1]*(m[i]/g));
        m[1] = m[1]*(m[i]/g);
        a[1] = (a[1]%m[1]+m[1])%m[1];
    }
    printf("%lld",a[1]);
	return 0;
}

（代码中的 qmul 是龟速乘）

Lucas定理

译名 ： 卢卡斯定理

用于解决大组合数取模问题的定理，要求模数必须为素数。

内容如下 ：

$$\binom{n}{m} ( \bmod p \; ) = \binom{n/p}{m/p} \times \binom{n \bmod p}{m \bmod p} \; ( \bmod p \; )$$

实现

代码通常这样写 ：

ll lucas(ll n,ll m,ll p)
{
    if(m == 0) return 1ll;
    return C(n % p,m % p,p) * lucas(n / p,m / p,p) % p;
}

其中 $C$ 是求组合数的函数，它的实现方式由题目数据范围而定。

时间复杂度是 $O(f(p)+g(n) \log \; n)$ ，其中 $f(n)$ 是预处理组合数的复杂度, $g(n)$ 是单次求组合数的复杂度。

证明

先推荐一篇写得很好的博客一份关于Lucas定理的简要证明（我就是从这看懂的）

首先需要两个引理 ：

引理一

$p$ 为质数，对于任意的 $k \in [1,p-1]$ ,我们有 ：

$$C_p^k \equiv 0 \; ( \bmod p \; )$$

证明 ：

$$C_p^k = \frac{p!}{k! \times (p-k)!}$$

因为 $p \bot k$ ，所以分子中不含有 $p$ 和 $p$ 的真因数，即不可约去 $p$ 这一项，于是原式的值有因子 $p$ ，在模 $p$ 意义下值为 $0$

引理二

$p$ 为质数，则对于任意正整数 $x$ 都有 ：

$$(1+x)^p \equiv 1 + x^p \; ( \bmod p \; )$$

证明需要用到二项式定理 ：

$$(1 + x) ^ p \equiv \prod_{i=0}^p c_p^i \cdot x^i \; ( \bmod p \; )$$

由引理一，可以约去 $C_p^1 \sim C_p^{p-1}$ 项，于是就有 ：

$$(1 + x) ^ p \equiv 1 + x^p \; ( \bmod p \; )$$

于是我们利用以上两个引理来证明Lucas定理 ：

由二项式定理，有 ：

$$(1 + x)^n \equiv \sum_{i = 0}^nC_n^i \cdot x_i \;( \bmod p \; )$$

我们使用带余除法，也就是 $n = q_n \cdot p + r_n , m = q_m \cdot p + r_m$ ，那么就有 ：

$$(1+x)^n \equiv (1+x) ^ {q_n \cdot p + r_n} \equiv [(1+x)^p]^{q_n} \cdot (1+x)^{r_n} \; ( \bmod p \; )$$

用二项式定理展开 ：

$$\sum_{i=0}^nC_n^i \cdot x_i \equiv \left( \sum_{j = 0}^{q_n} C_{q_n}^j \cdot x ^ {p \cdot j} \right ) \left ( \sum_{k = 0}^{r_n} C_{r_n}^k \cdot x ^ k \right )$$

此时我们观察这个式子 ：

$C_n^m$ 就是左式 $x^m$ 项的系数，它唯一对应着右侧 $j = p_m,k = r_m$ 的情况，因为只有此时能乘出来 $x^{p \cdot p_m} \cdot x^{r_m} = x^m$

我们把 $j,k$ 的取值代入，就有了 ：

$$C_n^m \equiv C_{q_n}^{q_m} \cdot C_{r_n}^{r_m} \equiv C_{\lfloor \frac{n}{p} \rfloor} ^ {\lfloor \frac{m}{p} \rfloor} \cdot C_{n \bmod p} ^ {m \bmod p} \; (\bmod p\; )$$

于是Lucas定理得证

扩展Lucas定理

(exLucas)

Lucas定理要求模数 $p$ 必须为素数，对于不是素数的模数 $p$ ，我们可以使用exLucas。

（以下部分来自marchkid_joe）：

1. 引入

在解决问题时，会遇到模数不是质数的情况，便又有了拓展卢卡斯的定理(EXLucas)。（拓展卢卡斯和卢卡斯没关系）。

仍然是这个问题，出题人又不保证 $p\in prime$。

$$C_{n}^{m}\bmod p \qquad p\in N^*$$

1. 具体流程

• 中国剩余定理
• 逆元

（可以看出 ExLucas 确实和 Lucas 一点关系没有。）

$(1)$.对于模数 $P$ 根据唯一分解定理，我们可以把 $P$ 拆为几个质数相乘的形式。

$$P=\displaystyle\prod_{i=1}^{n} p_i^{k_i}$$

$(2)$.因为现在拆成的几个质数的乘积之间一定两两互质，根据中国剩余定理，可以列出下面的式子：

$$\begin{cases} x&\equiv C_n^m(\bmod\,p_1^{k_1})\\ x&\equiv C_n^m(\bmod\,p_2^{k_2})\\ &\vdots\\ x&\equiv C_n^m(\bmod\,p_n^{k_n})\\ \end{cases}$$

$(3)$.解出每一个方程。

$(4)$.合并中国剩余定理。

1. 解释流程 (3)

相信大家最疑惑的一定是 $(3)$ 吧，我们随便拎出来一个式子：

$$C_n^m\bmod p^k=\frac{n!}{m!(n-m)!}\bmod p^k$$

阶乘内可能含有 $p$，无法求逆元怎么解决呢？

Answer :那就把 $p$ 提出来！

举个很经典的栗子

$22!,p=3,k=2,p^k=9$

$$\begin{aligned} 22! &\equiv(1\times 2\times 4\times 5\times 7\times 8)\\ &\times (10\times 11\times 13\times 14\times 16\times 17)\\ &\times (19\times 20\times 22)\\ &\times (3\times 6\times 9\times 12\times 15\times 18\times 21)(\bmod\,3^2)\\ &\equiv(1\times 2\times 4\times 5\times 7\times 8)^2\\ &\times (19\times 20\times 22)\\ &\times 3^7(1\times 2\times 3\times 4\times 5\times 6\times 7)(\bmod\,3^2)\\ \end{aligned}$$

我们可以发现这样一个规律：

可以将式子拆为四部分

• 提出来的 $p^x,x={\lfloor\frac{n}{p}\rfloor}$。
• 含有质因子为 $p$ 的数每个都提出一个 $p$ 后变成了 ${\lfloor\frac{n}{p}\rfloor}!$。
• 不含质因子但可以凑成以 $p^k$ 为单位的 ${\lfloor\frac{n}{p^k}\rfloor}$ 组数。
• 剩下的数字。

化成一个恶心的式子：

$$\begin{aligned} n!={\lfloor\frac{n}{p}\rfloor}!\times p^{\lfloor\frac{n}{p}\rfloor}\times ({\displaystyle\prod_{i=1\land i\nmid p}^{p^k}i})^{\lfloor\frac{n}{p^k}\rfloor}\times ({\displaystyle\prod_{i=p^k\times{\lfloor\frac{n}{p^k}\rfloor}+1\land i\nmid p}^{n}i}) \end{aligned}$$

我们发现 ${\lfloor\frac{n}{p}\rfloor}!$ 可以继续递归求解。

我们定义 $f(n)$ 为提完所有 $p$ 以后阶乘之和，定义函数 $g(n)$ 为从 $n!$ 提出来的 $p$ 的次幂。同样可以递归求解。

$$f(x)={f(\lfloor\frac{n}{p}\rfloor})\times({\displaystyle\prod_{i=1\land i\nmid p}^{p^k}i})^{\lfloor\frac{n}{p^k}\rfloor}\times({\displaystyle\prod_{i=p^k\times {\lfloor\frac{n}{p^k}\rfloor}+1\land i\nmid p}^{n}i})$$ $$g(n)=\lfloor\frac{n}{p}\rfloor+g(\lfloor\frac{n}{p}\rfloor)$$

对每一个阶乘进行操作，就得到了这个式子：

$$\frac{\frac{n!}{p^x}}{\frac{m!}{p^y}\times\frac{(n-m)!}{p^z}}\times p^{x-y-z}(\bmod\,p^k)$$ $$\frac{f(n)}{f(m)f(n-m)}p^{g(n)-g(n-m)-g(m)}(\bmod\,p^k)$$

此时我们发现：我们已经从所有阶乘中提尽了 $p$。

$$\because \gcd(p^k,f(m))=1 \land \gcd(p^k,f(n-m))=1$$

$\therefore f(m),f(n-m)$ 存在模 $p^k$ 意义下的逆元。

其中 $g(m)+g(n-m)\leqslant g(n)$ 一定成立。

简单说明一下，已知 $n\gt m$，先将 $n!$ 的前 $m$ 项消掉，剩下 $n-m$ 项为 $n\times (n-1)\times …\times (n-m+1)$，所以这剩下的 $n-m$ 项一定不小于 $(n-m)!$，因此 $g(m)+g(n-m)\leqslant g(n)$。

已经解决了最困难的一步，中国剩余定理等一些简单的东西可以参考前文。

成功了！

（引用完）

---

常用变换

注 ： 由于篇幅限制，以下关于狄利克雷卷积和莫比乌斯反演的例题及解析都放在了 莫比乌斯反演总结 一文中，那是对这一部分内容的专题强化。

Dirichlet卷积

译名就是狄利克雷卷积

1.定义 ： 对于两个数论函数 $f(x),g(x)$ ，定义他们的卷积为

$$(f*g)(n) = \sum_{d \mid n} f(d) \cdot g(\frac{n}{d})$$

2.性质：

1. 交换律: $f \ast g = g \ast f$
2. 结合律: $( f \ast g ) \ast h = f \ast ( g \ast h )$
3. 分配律: $f \ast ( g + h ) = f \ast g + f \ast h$
4. 单位元: $\varepsilon$ 表示 $[x=1]$ ，满足对任意函数 有 $\varepsilon * f = f$
5. 对积性函数: 若 $f$ 为积性， $g$ 为积性，则 $f*g$ 也为积性
6. 对积性函数: 若 $f$ 为积性， $f*g$ 也为积性，则 $g$ 为积性

3.常见卷积： 其中涉及到的数论函数详见数论函数总结

$$f*1 = \sum_{d \mid n} f(d)$$ $$id_k*1 = \sigma_k$$ $$\varphi * 1 = id$$ $$\mu * 1 = \varepsilon$$ $$id * \mu = \varphi$$ $$1 * 1 = \tau$$

若 $F = 1*f$ 则有

$$f = \mu * F$$

莫比乌斯反演

1.定义 ： 对于以下求和函数 ：

$$F(n) = \sum_{d \mid n} f(d)$$

有 ：

$$f(n) = \sum_{d\mid n}\mu(d)F(\frac{n}{d})$$

2.莫比乌斯等式 ：

$$\varepsilon(n) = \sum_{d \mid n}\mu(d)$$

（即 $\mu*1=\varepsilon$ ） 3.性质 ： 若 $F(n)$ 为积性函数，那么 $f(n)$ 也为积性函数。

年少不知学姐（长）好，清北学堂泪两行