内容摘要：

本文主要包含以下数论基础知识点：

整除、gcd 、lcm 、exgcd 、同余、同余方程
快速幂、费马小定理、逆元
埃式筛法、线性筛
欧拉函数、卢卡斯定理

感谢zh_dou学长的博客赞助（大概这篇文就是数论·易+oi-wiki罢

注：本文已经年久失修，由于本文内容已经分散在其他文章中进行了更新，这里给出链接：

Part1,2 : 数论杂谈

Part3 : 筛法，亚线性和线性

Part4 : 数论函数总结和数论算法、定理和常用变换

以上文章内容中对与本文重合的部分可能会有修改和补充。

但仍保留本文（因为如果啥时候得讲课可以把这个课件修一修拿来用）

Part 1

让我们从整除开始，这样对吧

定义：

设 $a,b\in Z,a \neq 0$。如果 $ \exists q \in Z$，使得 $b=aq$ ，那么就说 $b$ 可被 $a$ 整除，记作 $a \mid b$ ，且称 $b$ 是 $a$ 的倍， $a$ 是 $b$ 的约数（因数）。

$b$ 不被 $a$ 整除记作 $a \nmid b$ 。

任何正整数都是 $0$ 的约数。

找了找整除的定义，大概是能否整除的判断随着定义的范围而变化，下边的整除大多定义在整数域（或许有的在非负整数域罢）。

性质：

$a \mid b \Longleftrightarrow -a \mid b \Longleftrightarrow a \mid -b \Longleftrightarrow |a| \mid |b|$
$a \mid b \space \wedge b \mid c \Longrightarrow a \mid c$
$a \mid b \space \wedge a \mid c \Longleftrightarrow \forall x,y \in Z ,a \mid (xb+yc)$
$a \mid b \wedge b \mid a \Longrightarrow b = \pm a$
设 $m \neq 0$ ，那么 $a \mid b \Longleftrightarrow ma \mid mb$
设 $b \neq 0$ ，那么 $a \mid b \Longleftrightarrow |a| \le |b|$
设 $a \neq b,b = qa + c$ ，那么 $a \mid b \Longleftrightarrow a \mid c$

关于判断能否整除
上边这个对 OI 没什么用所以不打算讲（

0 是所有非零整数的倍数。对于任意非零整数，其约数只有有限个。

严格地说，没有任何数能被 $-1$ 整除——《具体数学》

显然约数（显然因数）：对于整数 $b \neq 0$，$\pm 1,\pm b$ 是 $b$ 的显然约数，当 $b = \pm 1$ 时， $b$ 只有两个显然约数。

对于整数 $b \neq 0$ ,$b$ 的其他约数称为真约数（真因数、非显然约数、非显然因数）。

约数的性质：

设整数 $b \neq 0$ .当 $d$ 遍历 $b$ 的全体约数的时候，$\frac{b}{d} $ 也遍历 $b$ 的全体约数。
设整数 $b > 0$，则当$d$ 遍历 $b$ 的全体约数的时候，$\frac{b}{d} $ 也遍历 $b$ 的全体正约数。

质数（素数）

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

$0$ 和 $1$ 既不是质数也不是合数。

性质

素数有无穷个

证明：

（经典反证法）假设只有 $n$ 个质数，他们构成一个质数集合 $P$ ，设 $N = \prod_{i=1}^n P_i$ ，那么 $N+1$ 是素数或合数

如果是，那么 $N+1$ 大于素数集合中的任意一个数，所以它不在假设的集合中。

如果不是，则它可以分解为有限个质数幂的乘积。因为 $N \bot N+1$ ，所以假设的质数集合中的任意一个质数都不能整除 $N+1$ ，那么在集合外一定还存在其他素数。

两种情况都与假设矛盾，于是不存在有限个质数组成质数集合。即质数有无穷个

素数数目的计算

素数定理

素数定理（prime number theorem）是素数分布理论的中心定理，是关于素数个数问题的一个命题：设 $x \ge 1$ ，以 $\pi(x)$ 表示不超过x的素数的个数，当 $x\rightarrow \infty$ 时， $π(x) \sim Li(x)$ 或 $π(x) \sim x/ln(x)$ 。（ $Li(x)$ 为对数积分）

$\pi(x) = Li(x) + O(xe^{-c\sqrt{\ln x}}) \; (x \rightarrow \infty)$

其中 $Li(x) = \int_{2}^{x} \frac{dt}{\ln t}$ ， $O(xe^{-c\sqrt{\ln x}})$
是误差估计

素数定理可以给出第 $n$ 个素数 $p(n)$ 的渐进估计： $p(n) \sim \frac{n}{\ln n}$。

它也给出从整数中抽到素数的概率。从不大于 $n$ 的自然数中随机选一个，他是素数的概率大约是 $\frac{1}{\ln n}$ 。

证明：看了一眼初等证明，然后放弃了（

在一个大于 $1$ 的数 $a$ 和它的 $2$ 倍之间（即 $(a,2a]$ ），必存在至少一个素数
存在任意长度的素数等差数列
一个偶数可以写成两个合数之和，其中每一个合数最多只有 $9$ 个质因数。
一个偶数必定可以写成一个质数加上一个合成数，其中合数的因子个数有上界。
一个偶数必定可以写成一个质数加上一个最多由 $5$ 个因子所组成的合成数。后来，有人简称这一结果为 $(1+5)$
一个充分大偶数必定可以写成一个素数加上一个最多由 $2$ 个质因子所组成的合成数。

gcd与lcm

互质

互质是公约数只有1的两个整数，叫做互质整数。公约数只有1的两个自然数，叫做互质自然数，后者是前者的特殊情形。
（摘自百度百科）

互质,若 $N$ 个整数的最大公因数是 $1$ ，则称这 $N$ 个整数互质。显然 $N$ 个数互质和这 $N$ 个数两两互质是不同的条件，并且后者比前者更强。

$1$ 和任何数都成倍数关系，但和任何数都互质

1和-1与所有整数互素，而且它们是唯一与0互素的整数。

通过有理数的表示方式 $x = \frac{p}{q} ,p \bot q $ 也可以看出 $0$ 与 $\pm 1$ 互质，否则 $0$ 不是有理数。

显然除 $1$ 之外，一个数和它本身不互质

最大公约数（gcd）

Greatest Common Divisor (gcd)

一组数的公约数就是指同时是这组数中每一个数的约数的数. $\pm 1$ 是任意一组整数的公约数.

最大公约数就是最大的公约数.

定义 $gcd(0,0) = 0$

性质：

$gcd(a,b) = gcd(a,a-b) = gcd(b,a-b)$(更相减损)
$gcd(2a,2b) = 2gcd(a,b)$

例题是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} )$ ,可以通过本题。

欧几里得算法

求gcd用的，大家应该都会写：

int gcd(int a,int b)
{
    return b ? gcd(b,a % b) : a;
}

这是经典的辗转相除，我还找到了经过归纳得出的非递归写法：

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

看起来很怪，但是应该是对的（尽管我没有对拍过）

当然也可以直接使用 __gcd()来得到GNU的支援（

证明的话我打算放在数论算法、定理和常用变换里头，这里就不展开说了，有兴趣的可以自己看看

裴蜀定理

（又称贝祖定理）

对于任意不全为零的整数$a,b$ 都 $\exists x,y \in Z$ ，使得 $ ax+by = gcd(x,y)$。
对于不定方程 $ax + by = m$ ，其有解的充要条件是 $gcd(a,b) \mid m$

证明同上（

应用：

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 = 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$ 中有且仅有一个可以被表示

(就是zerc前两天没证出来的对称性，事实是这玩意不光是对的，而且还是裴蜀定理的推论)

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

可表示的数与不可表示的数在区间 $[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 \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$ 不可能被表示。

此时若 $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$ 可以被表示。

所以我们证明了对称性

然后那道考试题的等价题目就是U238921
虽然这是一道魔改后的题目卡掉了原来的正解。
但是新的正解也不难的说（我一下午就看懂了

最小公倍数(lcm):

zh_dou : lcm 这东西在数论推柿子里因没有什么性质而遭到嫌弃

对于只有两个数的时候　：　

$lcm(i,j) = \frac{i * j}{gcd(i,j)}$

但是对于多个数不成立,显然多个数的gcd很可能会丢失一些重复出现的因子。
例题是： P1891

扩展欧几里得算法(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 \space mod \space b) = bx_2 + (a \space mod \space b)y_2 = bx_2 + (a - \lfloor \frac{a}{b}b \rfloor)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)$
则 $ lcm(a,b) = a * b / g$
又 $ ax + lcm(a,b) + by - 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;
int T;
int a,b,c;

void work();
ll gcd(ll ,ll );
ll exgcd(ll ,ll ,ll& ,ll& );

void main()
{
    scanf("%d",&T);
    while(T--) work();
    return;
}

inline void work()
{
    scanf("%d%d%d",&a,&b,&c);
    if(c % gcd(a,b)){
        puts("-1");
        return;
    }
    ll x,y;
    ll d = exgcd(a,b,x,y);
    x *= c / d;
    y *= c / d;
    ll p = b/d ,q = a/d ,k;
    if(x < 0)
    {
        k = ceil((1.0 - x) / p);
        x += p * k;
        y -= q * k;
    }
    else {
        k = (x - 1) / p;
        x -= p * k;
        y += q * k;
    }
    if(y > 0)
    {
        printf("%lld ",(y - 1) / q + 1);
        printf("%lld ",x);
        printf("%lld ",(y - 1) % q + 1);
        printf("%lld ",x + (y - 1) / q * p);
        printf("%lld\n",y);
    }
    else{
        printf("%lld ",x);
        printf("%lld\n",y + q * (ll) ceil((1.0 - y) / q));
    }
    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,x,y);
    ll t = x;
    x = y;
    y = t - (a/b) * y;
    return g;
}

ll gcd(ll a,ll b)
{
    return !b ? a : gcd(b,a % b);
}

}

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

exgcd就到这里

同余理论

对于两整数 $a,b$ ，若 $a \space mod \space p = b \space mod \space p$ ,则称 $a$ 与 $b$ 在模 $p$ 意义下同余

用符号表示就是熟悉的 $a \equiv b \space(\space mod \space p \space )$

性质

对称性： $a \equiv b \space(\space mod \space p) \Longrightarrow b \equiv a \space(\space mod \space p \space )$
可乘性： $a \equiv b \space(\space mod \space p) , c \equiv d \space(\space mod \space p \space ) \Longrightarrow ac \equiv bd \space(\space mod \space p \space )$

应用

应用较少，主要在定理的证明和表达中使用。

求解线性同余方程

线性同余方程是指形如 $ax \equiv b \space(\space mod \space p)$ 的方程，因为未知数的指数为 $1$ ，所以我们称之为一次同余方程或线性同余方程

解线性同余方程的方法是：把同余式 $a x\equiv b \space(\space mod \space p \space )$ 转化成 $ax + kp = b$ ，然后使用exgcd求解
对于同余式 $a \equiv 1 \space(\space mod \space p \space )$ 的一个解是 $a$ 在模 $p$ 意义下的逆元。逆元稍后解释。

对于线性同余方程组的解法则需用到中国剩余定理(CRT) 和扩展中国剩余定理(exCRT) ，详见数论算法、定理和常用变换

板子题是P1082

非常简单，直接放下代码罢

#include<bits/stdc++.h>
using namespace std;
long long a,b,x,y;
void exgcd(long long a,long long b){
    if(b == 0)  {x = 1,y = 0;return;}
    exgcd (b,a % b);
    long long m = x;
    x = y;
    y = m - (a / b) * y;
}
int main()
{
    cin>>a>>b;
    exgcd(a,b);
    x = (x % b + b) % b;
    cout<<x;
    return 0;
}

（早期马蜂，看起来可能挺离谱的）

求解高次同余方程

求解高次同余方程有 $a^x\equiv b \space(\space mod \space p)$ 和 $x^a\equiv b \space(\space mod \space p\space )$ 两类问题。

前者可以使用 Baby Step,Giant Step (BSGS)算法解决，后者我不知道（（（

所以照例详见数论算法、定理和常用变换

于是 Part1 结束了！

Part 2

这就是关于逆元的部分。
本来想扔一个数论杂谈的链接走人，但是觉得不太妥当。所以就把那里边的内容添点东西粘贴过来（

快速幂

作为逆元的前置知识排到这里罢。

快速幂就是对幂运算的二进制优化，使得计算 $x^k$ 的时间复杂度由 $O(k)$ 降为 $O(log \space k)$

具体做法就是对指数进行二进制拆分，把幂次转换成二进制正次幂乘积的形式，举一个zh_dou博客里的例子就是：

$105_{(10)} = 1101001_{(2)}$

所以

$x^{105} = x^{2^6+2^5+2^3+2^0} = x^{2^6} x^{2^5} x^{2^3} x^{2^0}$

代码实现非常短，应该都有肌肉记忆了（:

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

费马小定理

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

证明：

设一个质数 $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 (\space mod \space p\space )$

对性质的证明：

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

又因为每个 $(A_i \times a )\space (\space mod \space p\space ) $ 都不同，且 $(A_i \times a )\space (\space mod \space p\space ) < p $于是每一个 $A_i \times a $ 都对应了一个 $A_i$
所以 $(A_i \times a )\space (\space mod \space p\space ) $ 的取值取遍了 $[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} (\space mod \space p\space )$

$a^{p-1} \times f \equiv f (\space mod \space p\space )$

所以

$a^{p-1} \equiv 1 (\space mod \space p\space )$

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

乘法逆元

若 $a * x \equiv 1 (\space mod \space p\space )$
则x是a在模b意义下的逆元
大概是四种：

一、费马小定理：

若 $p \in prime,a\in N^*,a \perp p$ ，则有
$a^{p-1} \equiv 1 (\ mod \ p)$
所以显然 $a^{p-2}$ 即为所求。代码不放了，ksm板子应该都会

二、扩展欧几里得算法（exgcd）：

这个方法在单次查找中表现优异，要求少速度快。只要求 $a \perp p$ ，不要求 $p$ 是质数。（扩欧~~不鸽的话~~会写在数论算法、定理和常用变换中）。代码也很好写:

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;
}
x = (x % p + p) % p;

这样求得的 $x$ 就是要求的逆元。

三、线性求逆元：

适用于求多个连续数字的逆元，经典例题是 P3811
先放下代码：

1
2
3

inv[1] = 1;
for(int i = 2;i<=n;i++)
    inv[i] = (p - p/i) * inv[p % i] % p;

然后我们就有了 $1~n$ 范围内的数模 $p$ 的逆元。
证明的话……~~为什么不直接背过呢~~
我们已知 $1^{-1} \equiv 1 (mod \space p)$
然后设 $p = k * i + r,(i < r < i < p) ,(1<r<i<p)$ ，即 $k$ 是 $p/i$ 的商， $r$ 是余数。
再将这个式子放到模 $p$ 意义下就会得到：

$k \times i + r \equiv 0 \space ( \space mod \space p \space )$

然后乘上 $i^{-1}r^{-1}$ 就会得到：

$k \times r^{-1} + i^{-1} \equiv 0 \space ( \space mod \space p \space )$ $i^{-1} \equiv -k \times r^{-1} \space ( \space mod \space p \space )$ $i^{-1} \equiv - \lfloor \frac{p}{i} \rfloor \times ( \space p \space mod \space i \space )^{-1} \space ( \space mod \space p \space )$

于是我们就可以从前面推出当前的逆元了。

所以第二部分结束力

四、线性求任意 $n$ 个数的逆元

求给定数组 $a_i$ 中每一个元素的逆元：

首先计算这 $n$ 个数的前缀积数组 $S$ ,然后对 $S_n$ 进行一个单独的求逆元，得到逆元为 $Sv_n$ ，也就是这 $n$ 个数逆元的乘积。

然后进行一个倒推，每次用 $Sv_i$乘上 $a_i$ ，就可以得到 $Sv_{i-1}$ （因为 $i$ 和 $i^{-1}$ 消掉了）

然后我们就得到了逆元的前缀积数组 $Sv$

对于每次询问，我们只需要用 $S_{i-1} * Sv_i$ 就可以得到 $a_i$ 的逆元

Part 3

这里是基础筛法的部分。
~~所以我扔下一个链接走了筛法，亚线性与线性~~
所以我又把旧博客CV过来了（连自己都抄是吧）

埃氏筛(埃拉托斯特尼筛法)

埃氏筛的思想简单易懂：从小到大考虑范围内的每一个数，然后把质数的所有倍数都标记成合数，那么最后没有被标记的数就是质数了，下面给出代码：

//n为枚举上界，vis[i] == 1表示i为合数，p[]为质数数组，tot为质数个数，下同。
void Eratosthenes(int n)
{
    vis[0] = vis[1] = 1;
    for(int i = 2;i<=n;i++)
    {
        if(!vis[i]){
            p[++tot] = i;
            if(i * i <= n)
            for(int j = i*i;j<=n;j+=i) vis[j] = 1;
            //小优化，2~i-1的倍数之前已经筛过了，直接从i的倍数开始可以加快速度
        }
    }
}

带有优化的埃氏筛的时间复杂度为 $O(n \log \log n)$

欧拉筛

欧拉筛是质数的线性筛法，也经常用来预处理 $\varphi$ 和 $\mu$ 的值
欧拉筛的特点是每个数只被自己的最小质因子筛去，因此是线性算法(所以欧拉筛在筛出合数的同时可以求出每个合数的最小质因子)。
下面给出欧拉筛处理 $\varphi$ 和 $\mu$ 的代码(代码中未取模) ：

void euler(int n)
{
    mu[1] = phi[1] = 1;
    vis[0] = vis[1] = 1;
    for(int i = 2;i<=n;i++)
    {
        if(!vis[i]) {p[++tot] = i;mu[i] = -1;phi[i] = i-1;}
        for(int j = 1;j<=tot && i * p[j]<=n;j++)
        {
            vis[i * p[j]] = 1;
            if(i % p[j] == 0) {
                phi[i * p[j]] = phi[i] * p[j];
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = -mu[i];
            phi[i * p[j]] = phi[i] * (p[j]-1);
        }
    }
}

欧拉筛预处理 $\varphi$ 和 $\mu$ 的过程完全依赖于他们的性质，他们的性质在文章数论函数总结中有过提及。

第三部分就是这么短命。

Part 4

这里有一些数论函数和基础定理。

所以我当然要扔链接：
数论函数总结
 数论算法、定理和常用变换

数论函数

一、欧拉函数$\varphi(n)$

1.定义：小于$x$的正整数中与x互质的数的个数，即：

$\varphi(n) \sum_{i<n}[i \perp x]$

（任何数都与1互质）
其中约定$\varphi(1) = 1$

2.性质：

对于质数 $p$ ，$\varphi(p) = p-1$
显然，除了质数本身的数都与他互质
对于 $x = p^k,k \in N_{+}$ ,有 $\varphi(x) = (p-1) \times p^{k-1}$
证明：所有 $p$ 的倍数都与 $x$ 不互质，其他所有数都与 $x$ 互质，$1\sim x$ 中 $p$ 的倍数恰好有 $p^{k-1}$ 个（包括 $x$ ），所以 $\varphi(x) = p^k - p^{k-1} = (p-1) \times p^{k-1}$
欧拉函数是积性函数，即对于互质的两数 $p$ ， $q$ ，有 $\varphi(p \times q) = \varphi(p) \times \varphi(q)$
证明略
对于数 $x$ 分解质因数的结果是 $x = \prod_{i = 1}^{n} p_i^{k_i}$ ，有 $\varphi(x) = x \prod_{i = 1}^{n} (1 - \frac{1}{p_i} )$
证明：利用前几条定理代入即得
若 $p \mid x \ \&\&\ p\in prime$ ，有 $ \varphi(p \times x) = p \times \varphi(x) $
证明：使用性质4，连乘内容不变，前面 $x$ 变成 $p \times x$ 即得
若 $p \nmid x \ \&\&\ p \in prime $，有 $\varphi(p \times x) = (p-1) \times \varphi(x) $
证明： p与x互质，由积性函数得到
$\varphi * 1 = id$

3.求法：
对于单个欧拉函数求解可利用性质4分解质因数后求解
线性求欧拉函数则需要改一改欧拉筛，利用性质5、6求解：
筛去合数时，已知质数 $i$ 为其约数，判断 $p[j]$ 是否为 $i$ 的约数，由性质5、6求解。

for(int i = 2;i<=n;i++)
{
    if(!vis[i]) phi[i] = i-1,p[++tot] = i;  
    for(int j = 1;j<=tot && i * p[j] <= n;j++)
    {
        int nx = i * p[j];
        vis[nx] = 1;
        if(i % p[j]) phi[nx] = phi[i] * (p[j] - 1);
        else{
            phi[nx] = phi[i] * p[j];
            break;
        }
    }
}

4.应用：
扩展欧拉定理：

$a^{b} \equiv\left\{\begin{array}{ll} a^{b \bmod \varphi(p)} & a \perp p \\ a^{b} & a \not \perp p, b<\varphi(p) \quad(\bmod p) \\ a^{b \bmod \varphi(p)+\varphi(p)} & a \not \perp p, b \geq \varphi(p) \end{array}\right.$

证明……这个
可以降幂用，比方说luogu上头那道古代猪文

二、莫比乌斯函数$\mu(n)$

1.定义：

$\mu(n)=\left\{\begin{array}{c} &1, &n=1 \\ &(-1)^{k}, &n=p_{1} \cdot p_{2} \cdot \ldots \cdot p_{k} \\ &0, &\text { otherwise } \end{array}\right.$

2.性质：

积性函数
与欧拉函数： $\sum_{d \mid n}\frac{\mu(d)}{d} = \frac{\varphi(n)}{n}$ 证明：令
与组合数： $\sum_{d \mid n} \mu(d)=\sum_{i=0}^{k}\left(\begin{array}{l} k \\ i \end{array}\right) \cdot(-1)^{i}=\left\{\begin{array}{l} 1, n=1 \\ 0, n>1 \end{array}\right.$
$\mu * 1 = \varepsilon $ $\sum_{d\mid n}\mu(d) = \left\{\begin{array}{c} &1&(n=1) \\ &0&(n=0) \end{array}\right.$
$id * \mu = \varphi $
无穷级数（没见用过）： $\sum_{n = 1}^{\infty} \frac{\mu(n)}{n} = 0\\ \sum_{n = 1}^{\infty} \frac{\mu(n) \cdot ln(n)}{n} = -1\\ \sum_{n = 1}^{\infty} \frac{\mu(n) \cdot x^n}{1-x^n} = x\\$

三、幂函数$id^k(n)$

1.定义：

$id_k(n) = n^k$

特别地，当 $k = 1$ 时， $id(n) = n$ 被称为单位函数（也称恒等函数），当$k = 0$时，函数变为 $1(n) = 1$ ，是常数函数

2.性质：

完全积性

四、因子个数函数$ \tau(n) $

1.定义：因子个数函数$\tau$定义为正整数$n$的所有正因子个数

$\tau(n) = \sum_{d \mid n}1$

或

$\tau(n) = \sum_{i=1}^{n}[d\mid n]$

五、除数函数$\sigma(n)$

1.定义：

$\sigma_k(n) = \sum_{d\mid n}d^k$

其中$k = 0$时通常简记作$d(n)$或$\tau(n)$，即因子个数函数，$k = 1$时通常简记作$\sigma(n)$

六、单位函数$\varepsilon(n)$

1.定义：

$\varepsilon(n) = [n = 1]$

2.性质：
完全积性

数论函数我目前就整理了这些，欢迎补充。

基础定理

卢卡斯定理

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

内容如下：

$\binom{n}{m} (\; mod \; p\; ) = \binom{n/p}{m/p} \times \binom{n \; mod \;p}{m \; mod \; p} \; (\; mod\; 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)$ 是单次求组合数的复杂度。

证明

不打算讲证明，所以还是放到专门的文章里罢

我滴任务，完成啦！

所以按照进度是讲完了，但是还可以再说一点大家都会的东西：

参考资料：

oi-wiki
WeLikeStudying’s blog
zh_dou’s blog
suxxsfe’s blog
P5656官方题解
还有挂的链接的文章里的链接（

内容摘要 ：

Part 1

让我们从整除开始，这样对吧

定义：

性质：

质数（素数）

性质

素数数目的计算

素数定理

gcd与lcm

互质

最大公约数（gcd）

性质 ：

欧几里得算法

裴蜀定理

应用 ：

一些推论 ：

最小公倍数(lcm):

扩展欧几里得算法(exgcd)

推导

代码实现

例题

同余理论

性质

应用

求解线性同余方程

求解高次同余方程

Part 2

快速幂

费马小定理

证明 ：

乘法逆元

一、费马小定理 ：

二、扩展欧几里得算法（exgcd）：

三、线性求逆元 ：

四、线性求任意 $n$ 个数的逆元

Part 3

埃氏筛(埃拉托斯特尼筛法)

欧拉筛

Part 4

数论函数

一、欧拉函数$\varphi(n)$

二、莫比乌斯函数$\mu(n)$

三、幂函数$id^k(n)$

四、因子个数函数$ \tau(n) $

五、除数函数$\sigma(n)$

六、单位函数$\varepsilon(n)$

基础定理

卢卡斯定理

实现

证明

参考资料 ：

内容摘要：

性质：

应用：

一些推论：

证明：

一、费马小定理：

三、线性求逆元：

参考资料：