数论

常见概念和符号

整除/同余常见符号

1. 整除符号 $x\mid y$，表示 $x$ 整除 $y$ ，即 $x$ 是 $y$ 的因数

2. 取模符号 $x \bmod y$ ，表示 $x$ 除以 $y$ 以后的余数

3. 互质符号 $x~\bot~y$ ，表示 $x$ ，$y$ 互质

4. 最大公约数 $\gcd(x,y)$

5. 最小公倍数 $\text{lcm} (x,y)$

数论函数常见符号

求和符号：$\sum$ 符号，表示满足特定条件的数的和

1. $\sum _{i=1} ^{n} ai$ 表示 $a_1\sim a_n$ 的和

2. $\sum_{S\subseteq T} |S|$

求积符号：$\Pi$ 符号，表示满足特定条件的数的积

1. $\Pi_{i=1}^n$ 表示 $n!$
2. $\Pi _{i=1}^{n} a_i$ 表示从 $a_1\sim a_n$ 的积
3. $\Pi _{x\mid d} x$ 表示 $d$ 的所有因数的乘积

整除符号：$\mid$ ，$a \mid b$ 表示 $a$ 是 $b$ 的约数 $b$ 不被 $a$ 整除记作 $a \nmid b$ 。

同余符号：$\equiv$ ，$a\equiv b \pmod c$ 表示 $\dfrac a c -\lfloor \dfrac a c \rfloor=\dfrac b c-\lfloor \dfrac b c \rfloor$ 或者说 $a/c$ 和 $b/c$ 的余数相同

数论函数

数论函数指定义域为正整数的函数。数论函数也可以视作一个数列。

积性函数

若 $f(n)$ 表示 $f(1)=1$ 且 $\forall x,y \in N_+$ $\gcd(x,y)=1$ 都有 $f(xy)=f(x)f(y)$，则 $f(n)$ 为积性函数

若 $f(n)$ 表示 $f(1)=1$ 且 $\forall x,y \in N_+$ 都有 $f(xy)=f(x)f(y)$，则 $f(n)$ 为完全积性函数

导数公式

$(C)^{‘}=0$ $(x^\mu)’=\mu x^{\mu-1}$

$(a^x)’=a^x\ln x$ ( $a$ 为常数） $(\sin x)’=\cos x$

$(\cos x)’=-\sin x$ $(\tan x)’=\sec^2x$

$(\cot x)’=-\csc^2x$ $(\sec x)’=\sec x \cot x$

$(\csc x)’=-\csc x\cot x$ $(\ln x)’=\dfrac{1}{x}$

$({\log_a}^x)’=\dfrac{1}{x\ln a}$ $(e^x)’=e^x$

加减公式：

$(u\pm v)’=u’\pm v’$ $(Cu)’=Cu’$ （C是常数）

$(uv)’=u’v+uv’$ $(\dfrac{u}{v})’=(\dfrac{u’v-uv’}{v^2})$

复数

设$a,b$为实数，$i^2=-1$，形如$a+bi$的数叫复数，其中$i$被称为虚数单位，复数域是目前已知最大的域

在复平面中，$x$ 代表实数，$y$ 轴（除原点外的点）代表虚数，从原点$(0,0)$到$(a,b)$的向量表示复数$a+bi$

模长：从原点$(0,0)$到点$(a,b)$的距离，即$\sqrt{a^2+b^2}$

幅角：假设以逆时针为正方向，从xx轴正半轴到已知向量的转角的有向角叫做幅角

计算：平行四边形法则(其实就是分配律)，注意这里的$i^2$为-1：

几何定义：复数相乘，模长相乘，幅角相加(至今我也没看懂)

$(a+bi)\times (c+di)=ac+bdi^2+bci+adi=ac-bd+(bc+ad)i$

同时，我们由向量的知识迁移到复数上来，定义 复数的模 就是复数所对应的向量的模。

复数 $z=a+bi$ 的模 $|z|=\sqrt{a^2+b^2}$

于是为了方便，我们常把复数 $z=a+bi$ 称为点 $Z$

由向量的知识我们发现，虚数不可以比较大小

复数满足交换律，结合律，对加法的分配律

当两个虚数实部相等，虚部互为相反数时，这两个复数互为 共轭复数。

即 $z=a+bi$ 的共轭复数为 $z=a-bi$

位运算

一般均是在二进制下来说

基本运算

1.与 (&) 两个对应位都为 $1$ 时才为 $1$

2.或 (|) 只要两个对应位中有一个 $1$ 时就为 $1$

3.异或(^) 只有两个对应位不同时才为 $1$

取反(~)

把0变成1，把1变成0

补码：在二进制表示下，正数和 的补码为其本身，负数的补码是将其对应正数按位取反后加一。

应用：$\text{lowbit}(x)=(x)\&(-x)$ 取出最后一个等于1的位数，具体原因想一想

左移和右移

num<<i 表示将 $num$ 的二进制表示向左移动1位所得的值。

num>>i 表示将 $num$ 的二进制表示向右移动1位所得的值。

注意：+ 和-的优先级高于左移右移

高精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<cstdlib>
#include<algorithm>
#define base 100000
#define cut 5
#define L 10000
using namespace std;

struct Big{
    int len;
    long long num[L];
    Big(){
        len=1;
        memset(num,0,sizeof(num));
    }
    Big operator=(const Big &a){
        len=a.len;
        for(int i=0;i<len;i++) num[i]=a.num[i];
        return *this;
    }
    long long &operator[](int a){
        return num[a];
    }
    long long operator[](int a)const{
        return num[a];
    }
    friend istream&operator>>(istream&,Big&);
    friend ostream&operator<<(ostream&,Big&);
};

int operator>(const Big a,const Big b){
    if(a.len!=b.len){
        if(a.len>b.len) return 1;
        return 0;
    }
    for(int i=a.len-1;i>=0;i--)
	    if(a[i]>b[i]) return 1;
    return 0;
}

int operator==(const Big a,const Big b){
    if(a.len!=b.len) return 0;
    for(int i=0;i<a.len;i++)
     if(a[i]!=b[i])
      return 0;
    return 1;
}

int operator<(const Big a,const Big b){
    if(a>b || a==b)return 0;
    return 1;
}

Big operator+(Big a,Big b){
    Big ret;
    long long carry=0;
    for(int i=0;;i++){
        ret[i]=a[i]+b[i]+carry;
        carry=ret[i]/base;
        ret[i]%=base;
        if(i>=a.len&&i>=b.len&&carry==0)
         break;
    }
    ret.len=min(L,max(a.len,b.len)+10);
    while(ret.len>0&&ret[ret.len-1]==0)
     ret.len--;
    if(ret.len==0)
     ret.len=1;
    return ret;
}

Big operator+(Big a,int b){
    long long carry=b;
    for(int i=0;;i++){
        a[i]+=carry;
        carry=a[i]/base;
        a[i]%=base;
        if(a[i]==0 && carry==0 && i>=a.len)
         break;
    }
    a.len=min(L,a.len+10);
    while(a.len>0 && a[a.len-1]==0) a.len--;
    return a;
}

Big operator*(Big a,Big b){
    Big ret;
    for(int i=0;i<a.len;i++)
        for(int j=0;j<b.len;j++) ret[i+j]+=a[i]*b[j];
    long long carry=0;
    for(int i=0;;i++){
        ret[i]+=carry;
        carry=ret[i]/base;
        ret[i]%=base;
        if(ret[i]==0 && carry==0 && i>=a.len+b.len-1) break;
    }
    a.len=min(L,a.len+b.len+10);
    while(a.len>0 && a[a.len-1]==0) a.len--;
    return a;
}

Big operator*(Big a,int b){
    long long carry=0;
    for(int i=0;;i++){
        carry+=a[i]*b;
        a[i]=carry%base;
        carry/=base;
        if(carry==0&&a[i]==0&&i>=a.len) break;
    }
    a.len=min(L,a.len+10);
    while(a.len>0&&a[a.len-1]==0) a.len--;
    return a;
}

Big operator-(Big a,Big b){
    long long carry=0;
    for(int i=0;;i++){
        a[i]-=b[i]+carry;
        if(a[i]<0) carry=(-a[i]/base+1);
        else carry=0;
        a[i]+=carry*base;
        if(carry==0&&i>=b.len) break;
    }
    while(a.len>0&&a[a.len-1]==0) a.len--;
    return a;
}

Big operator-(Big a,int b){
    long long carry=b;
    for(int i=0;;i++){
        a[i]-=carry;
        if(a[i]<0) carry=(-a[i]/base+1);
        else carry=0;
        a[i]+=carry*base;
        if(carry==0) break;
    }
    while(a.len>0 && a[a.len-1]==0) a.len--;
    return a;
}

Big operator/(Big a,int b){
     long long carry=0;
     for(int i=a.len-1;i>=0;i--){
         a[i]+=carry*base;
         carry=a[i]%b;
         a[i]/=b;
     }
     while(a.len>0&&a[a.len-1]==0) a.len--;
     return a;
}

Big operator%(const Big a,int b){
     return a-(a/b)*b;
}

int main(){
    return 0;
}

数论

整除性质

同余性质

最大公约数与最小公倍数

若干个数所有约数中的共同的最大数是最大公约数，倍数中共同的最小数是最小公倍数

一般两个数的最大公约数是 $\gcd$ 最小公倍数是 $\mathrm{lcm}$

$\gcd(a,b)\mathrm{lcm}(a,b)=ab$

求法：辗转相除

1

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

整除分块

整除分块是用于快速处理形似

的式子的办法

引理1

证明略

引理2

对于一个较大的 $n$ 我们显然会发现，我们后面的这个下取整取值并不是每一次都随着 $i$ 而变化的，它是呈块状分布的，同时这个下取整的值我们也能得到，应该是共有 $2\sqrt n$ 个值

结论：

通过严谨的数学推理(打表) 我们发现实际上这些取值是有规律的，即

如果一个块的开始位置时 $l$ 那么它的结束位置 $r$ 就是 $\lfloor \dfrac n {\lfloor \frac n l \rfloor} \rfloor$

那么我们写程序的基本结构就很显然了

1

for(int l=1,r;l<=n;l=r+1) r=n/(n/l);

所以我们对于形如：

可以对 $f(i)$ 可以直接前缀和预处理，就可以解决这道问题了

欧拉函数

$φ(n)$ :定义：1~n中与n互质的数的个数

公式：

莫比乌斯函数

我们一般表示为 $\mu(x)$

1. $\exists d_i\ge 2$，$\mu(x)=0$
2. $\forall d_i=1$，$\mu(x)=(-1)^k$ ($k$ 是质因数分解后有几项)
3. $x=1$ ，$\mu(x)=1$

如：

$\mu(6)=1$ $\mu(7)=-1$ $\mu(8)=0$

设 $s(n)=\sum_{i=d\mid n}^{n} \mu (i)$

如 $s(6) = \mu(1) +\mu(2) +\mu(3) +\mu(6)$

那么：

1. 当 $n=1$，$s(n)=1$
2. 当 $n>1$，$s(n)=0$

对于2的证明：

首先我们对于 $n$ 因式分解：$n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times\dots\times p_k^{\alpha_k}$ ($k\ge 1$)

那么我们的每一个 $d$ 都有：$d=p_1^{\beta_1}\times p_2^{\beta_2}\times\dots\times p_k^{\beta_k}$ ($\forall i \in [1,k]$ $0\le\beta_i\le \alpha_i$)

那么我们算一下 $\mu(d)$ 可知，我们只需要考虑，如果$\exists i \in [1,k]$，$\beta_i\ge 2$ 则原式为0

所以我们只需要看里面有多少个1即可

所以我们用组合数算一下：

我们这时候看一下二项式定理：

钦定 $a=1$ $b=-1$

所以 $\mu(x)$ 必然等于=0，得证

各种筛法

埃氏筛

用于统计从1-n中的质数

原理：从前往后筛，如果筛到一个数$i$，然后把$i$的倍数都删了

时间复杂度：$O(nlog^2n)$ 基本可以跑到3e5

1
2
3
4
5
6
7
8

void statistics(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) prime[++k]=i;
        for(int j=1;prime[j]*i<=n;j++){
            st[prime[j]*i]=true;
        }
    }
}

线性筛

这个东西很重要，关系到后面的积性函数求解

先放一个代码：

1
2
3
4
5
6
7
8
9

void primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) prime[++k]=i;
        for(int j=1;prime[j]*i<=n;j++){
            st[i*prime[j]]=true;
            if(!(i%prime[j])) break;
        }
    }
}

我们观察和上面那个的区别

发现无非就是多了一行if(i%prime[j]==0) break;

我们先给个证明来说明这句话加上后的正确性

证明

当$i$是$prime[j]$的整数倍时$\iff prime[j]\mid i$

设 $k=i/prime[j]$

则 $iprime[j+1]=prime[j](prime[j+1]*k)$

所以说 $i*prime[j]$ 是 $prime[j]$ 的整数倍

不需要继续标记

对于 $prime[j+2]*i$ 等同理，所以说可以直接跳出循环，不需要重新标记

这样线性筛的复杂度就可以被优化到 $O(n)$ 了

欧拉筛

我们可以把这件求phi分成两步

k是质数

首先我们容易发现一个问题：如果$k$是质数，那么$\varphi (k)$显然等于$k-1$，因为小于$k$的数都与$k$互质

所以我们可以把这一句：if(!vis[i]) p[++num]=i;再加上一句phi[i]=i-1;

1. $i\%p=0$ 时

   然后我们需要证明一个东西：

   若$p\mid i$且$p$为质数 则 $\varphi(ip)$=$p\varphi(i)$

   证明：

   若$p \mid i$ 则可以推出$p$ 是 $i$ 的一个质因子

   我们发现：一个数的欧拉函数与每一项的次数无关

   所以说

   $$\varphi(i*p)=i*p*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k})$$

   同时

   $$\varphi(i)=i*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k})$$

   发现两个式子除了 $i*p$ 全部相同

   所以我们可以推出 $\varphi(ip)$=$p\varphi(i)$

   证毕

   那么很显然在这一句中if(i%prime[j]==0) break;我们可以加上phi[prime[j]*i]=prime[j]*phi[i]

2. $i\%p!=0$ 时

   $p$ 一定是 $i*p_j$ 的最小质因子

   先把 $\varphi(i)$ 的式子摆在这

   $$\varphi(i)=i*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k})$$

   然后

   $$\varphi(p*i)=p*i*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_k}*(1-\frac{1}{p}))$$

   我们把下面的式子除以上面的式子发现：

   $$\varphi(p*i)/\varphi(i)=p*(1-\frac{1}{p})=p-1$$

   把 $\varphi(i)$ 挪到右边最后可以得到

   $$\varphi(p*i)=\varphi(i)*(p-1)$$

   所以我们讨论完了所有的情况，可以得到最终式子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

inline void get_euler(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            phi[i]=i-1;
            prime[++cnt]=i;
        }
        for(int j=1;prime[j]*i<=n && j<=cnt;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=prime[j]*phi[i];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}

莫比乌斯筛

这个比较简单，就不写了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

inline void get_euler(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            mu[i]=-
            phi[i]=i-1;
            prime[++cnt]=i;
        }
        for(int j=1;prime[j]*i<=n && j<=cnt;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=prime[j]*phi[i];
                break;
            }
            mu[i*prime[j]]=-mu[i];
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}

分解质因数

试除法

用于单个数检验是否为质数

原理：从1枚举到$\sqrt n$观察是否有数能被n整除

1
2
3
4
5
6
7
8
9

void prime(int x){
    int n=x;
    for(int i=2;i*i<=n;i++){
        if(x%i==0) 
            while(n%i==0) 
                vec[x].push_back(i),n/=i;
    }
    if(n) vec[x].push_back(n);
}

Miller-Rabin

用法：$O(k\log^2n)$ 判断 $n$ 是否是质数。其中 $k$ 是枚举底数的个数，$2^{78}$ 以内只需要枚举 $12$ 个。

费马小定理：

若 $p$ 是质数且 $p \nmid a$

我们可以根据费马小定理得出一种检验素数的思路(Fermat 素性测试)：

它的基本思想是不断地选取在 $[2,n)$ 中的 $a$，并检验是否每次都有 $a^{n−1}\equiv 1 \pmod n$

但是很遗憾，费马小定理的逆定理并不成立

卡迈克尔数：如果有一个合数 $n$ 满足任何一个 $a$ 都满足 $a^{n−1}\equiv 1 \pmod n$，那么我们称这个合数 $n$ 为卡迈克尔数，同时，满足 $m=2^n-1$ 那么 $m$ 还是卡迈克尔数，所以卡迈克尔数是无穷的

二次探测定理：

若 $p$ 是奇素数，则 $x^2 \equiv 1 \pmod p$ 的解为 $x=1$ 或 $x=p-1$ $\pmod p$

算法流程：

（1）对于偶数和 0，1，2 可以直接判断。

（2）设要测试的数为 $x$，我们取一个较小的质数 $a$，设 $s,t$，满足$2^s\times t=x-1$ （其中 $t$ 是奇数）。

（3）我们先算出 $a^t$，然后不断地平方并且进行二次探测（进行 $s$ 次）。

（4）最后我们根据费马小定律，如果最后 $a^{x-1}\not\equiv 1 \pmod x$，则说明 $x$ 为合数。

（5）多次取不同的 $a$ 进行 $Miller-Rabin$ 素数测试，这样可以使正确性更高

备注：

（1）我们可以多选择几个 $a$，如果全部通过，那么 $x$ 大概率是质数。

（2）$Miller-Rabin$ 素数测试中，“大概率”意味着概率非常大，基本上可以放心使用。

（3）当 $a$ 取前12个素数时，可以证明 $2^{78}$ 范围内的数不会出错。

（5）另外，如果是求一个 $\text{long long}$ 类型的平方，可能会爆掉，因此有时我们要用快速乘，不能直接乘。

$\text{Pollard-Rho}$ 先咕了

裴蜀定理

对于二元一次方程 $ax+by=c$，有整数解的充要条件是 $\gcd(a,b) \mid c$。

推论：当 $ax+by=1$ 时，当且仅当 $\gcd(a,b)=1$ 时有解。

证明：

设 $d=\gcd(a,b)$ 则 $d \mid a,d\mid b$。由整除的性质 $\forall x,y\in Z$，有 $d \mid (ax+by)。$

设 $s$ 为 $ax+by$ 最小正值，令 $q=\left\lfloor \dfrac{a}{s} \right\rfloor$。

则 $r=a\pmod s=a-q(ax+by)=a(1-qx)+b(-qy)$。

可见 $r$ 也为的线性组合。

由于 $r$ 为 $a\pmod s$ 所得，所以 $0\leq r<s$。

由于 $s$ 为线性组合的最小正值,可知。

1. 因此有 $s\mid a$ ，同理 $s\mid b$ ，因此，$s$ 是 $a$ 与 $b$ 的公约数，所以 $d\ge s$。

   因为 $d\mid a$ ，$d\mid b$ ，且 $s$ 是 $a$ 与 $b$ 的一个线性组合，所以由整除性质知 $d\mid s$。

2. 但由于 $d\mid s$ 和 $s>0$，因此 $d\le s$。

由 1,2 得 $d=s$ ，命题得证。

exgcd

现在我们对于 $ax+by=c$ 想要获得一组整数解。

首先 $c$ 肯定是要满足 $\gcd(a,b) \mid c$ 的（要不然裴蜀定理白证明了）。

然后我们可以直接求 $a_1x+b_1y=\gcd(a_1,b_1)$ 的一组整数解，最后 $x,y$ 再乘上 $c/\gcd(a_1,b_1)$ 即可

好了，我们现在说怎么求解。

当 $b=0$ 时，显然 $x=1,y=0$

当 $b\not= 0$ 时，有：

$ax+by=\gcd(a,b)$

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

$\therefore a x + b y = \gcd ( a , b ) = \gcd ( b , a \bmod b ) = b \times t x + ( a \bmod b ) \times t y$

$\because a \bmod b=a- \left\lfloor \dfrac{a}{b} \right\rfloor\times b$

$\therefore a x+b y=b\times tx+(a- \left\lfloor \dfrac{a}{b} \right\rfloor\times b)\times ty=a\times ty+b\times(tx−\left\lfloor \dfrac{a}{b} \right\rfloor\times ty)$

$\therefore x=ty,y=tx-\left\lfloor \dfrac{a}{b} \right\rfloor\times ty$

此时我们容易发现： $x$ 和 $y$ 都被转化成了两个更小的数，然后递归求解即可

1

#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#define ll long long using namespace std;ll exgcd(ll a,ll b,ll &x,ll &y){	if(!b){		x=1;y=0;		return a;	}	else{		ll tx,ty;		ll d=exgcd(b,a%b,tx,ty);		x=ty;y=tx-(a/b)*ty;		return d;	}}int main(){	ll a,b,k,x,y;scanf("%lld%lld%lld",&a,&b,&k);	ll d=exgcd(a,b,x,y);	if(k%d){puts("no solution!");return 0;}	else{		x=x*k/d;		y=(k-a*x)/b;	}	printf("%lld %lld\n",x,y);	return 0;}

欧拉定理

证明：

设 $x_1,x_2,\dots,x_{\varphi(m)}$ 是 $[1,m]$ 里面与 $m$ 互质的数，由于在 $\bmod m$ 意义下两两不同且余数都与 $m$ 互质

因此我们推理：$ax_i$ 必定也是 $\bmod m$ 意义下两两不同且余数都与 $m$ 互质的数

所以：

拓展欧拉定理

推理：Oi Wiki)

乘法逆元

定义：若 $ax\equiv 1\pmod b$ 且 $a$ 与 $b$ 互质，那么我们就能定义 $x$ 为 $a$ 的逆元，记为 $a^{-1}$ ，所以我们也能称 $x$ 为 $a$ 在 $\pmod b$ 意义下的倒数，此时我们对于 $\dfrac{a}{b}~\pmod p$，我们就可以求出 $b$ 在 $\pmod p$ 意义下的逆元，来代替 $\dfrac{1}{b}$

快速幂

由费马小定理：若 $p$ 为素数，$a$ 为正整数，且 $a$ 、$p$ 互质。则有 $a^{p-1}\equiv 1\pmod p$

所以

所以我们用快速幂算出来 $a\times b^{p-2}$ 就有 $\dfrac{a}{b}$ 的逆元的值了

1

#include<iostream>#include<cstdio>#include<queue>#include<algorithm>#include<cstring>#include<cmath>using namespace std;typedef long long ll;int mod;ll power(ll k,ll p){	ll ans=1;	while(p){		if(p&1) ans=ans*k%mod;		k=k*k%mod;		p>>=1;	}	return ans;}ll a,b;int main(){	scanf("%lld%lld",&a,&mod);//算a的逆元	printf("%lld",a*power(b,mod-2)%mod);	return 0;}

拓展欧几里得

求解 $ax\equiv c \pmod b$ 中 $c=1$ 的情况。我们可以转化为求解 $ax+by=1$ 的解

所以：

1

ll exgcd(ll a,ll b,ll &x,ll &y){	if(!b){		x=1;y=0;		return a;	}	else{		ll tx,ty;		ll d=exgcd(b,a%b,tx,ty);		x=ty;y=tx-(a/b)*ty;		return d;	}}int a,p,x,y;int main(){    scanf("%d%d",&a,&p);    int d=exgcd(a,p,x,y);    x=(x%p+p)%p;}

线性求逆元

首先，我们设 $p=kx+r$

那么我们很容易发现：$kx+r\equiv 0\pmod p$

此时，我们左右同时乘上 $k^{-1}r^{-1}$ 可得

$kr^{-1}+x^{-1}\equiv 0\pmod p$

$\therefore x^{-1}\equiv -kr^{-1}\pmod p$

把 $k=\left\lfloor \dfrac{p}{x} \right\rfloor$ $r=p \bmod x$ 代入，得

$x^{-1}\equiv -\left\lfloor \dfrac{p}{x} \right\rfloor \times (p \bmod i)^{-1} \pmod p$

阶乘求逆元

首先，有如下的一个关系：

$inv_{i+1}=\dfrac{1}{(i+1)!}$

$inv_{i+1}*(i+1)=\dfrac{1}{i!}\times \dfrac{1}{n+1}\times (n+1)=\dfrac{1}{i!}=inv_i^{-1}$

所以我们可以先求出 $n$ 的逆元，然后逆推即可

同时，我们也可以发现 $\dfrac{1}{i}$ 的逆元就是：$\dfrac{1}{i!}\times (i-1)!=\dfrac{1}{n}\pmod p$

Lucas

定理：

中国剩余定理(CRT)

定理：对于下列一些式子的整数求出符合条件的最小的正整数 $x$

首先，若$(m_1,m_2\dots m_n)$两两互质

我们即可直接令 $M=m_1\times m_2\dots\times m_n$

则令 $M_i=\dfrac{M}{m_i}$

当 $x$ 满足 $x = x_1\times M_1\times M_1^{-1}+x_2\times M_2\times M_2^{-1}\dots$ 时

一定符合上面的式子

莫比乌斯反演

形式一：

证明：

我们容易发现：对于右边的式子 $\sum_{i\mid x}g(i) \sum_{d\mid \frac x i} \mu(d)$

结合莫比乌斯函数刚才推的性质2，我们很容易得到该式 $=f(x)$

得证

形式二：