NOIP 数论
lalaji2010
·
2024-08-09 13:02:07
·
算法·理论
本 Blog 对数论里的基础概念和定义不作过多解释 ，如果觉得阅读有困难，可以先看 oiwiki-数论基础。
不说废话，我们开始。不然赶不上 SDSC 2024 3h 速通 NOIP 数论的速度了。
欧几里得算法
作为世界上已知被提出最早的算法，欧几里得算法在数论中扮演着一个非常重要的角色。
欧几里得算法也就是我们常说的辗转相除法 ，用于求最大公约数(gcd)。
注：a,b 的最大公约数可表示为 (a,b) 。
引理：(a,b)= (b,a \bmod b)
详细证明请见 这里。
此处给出不严谨简要证明。
假设a>b ，(a,b)=c ，则显然 c\mid(a-b)
当然 c\mid(a-kb) ，kb \leq a ，当 k 取 max 时，a-kb=a \bmod b 。
所以 c \mid b ，c\mid(a \bmod b) 。
我们设的 c=(a,b) ，那么必不可能 有 d\mid(a \bmod b) 且 d\mid b 且 d>c ，因为这样会有 d\mid a 且 d\mid b 且 d>c ，与假设 c=(a,b) 矛盾 。
\Rightarrow (a,b)= (b, a \bmod b)
欧几里得算法：
由于 (a,b)= (b, a \bmod b) 成立。
那么递归直到 b=0 ，此时 (a,0)=a 即为所求 gcd。
时间复杂度 O(\log w) ，w 表示值域。
code
inline int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}当然也可以使用内置的 __gcd(a,b) 函数。
最大公约数与最小公倍数的几个小性质
·(kn,km)=k(n,m),\operatorname{lcm}(kn,km)=k \operatorname{lcm}(n,m)
·若 a \perp b ，则 (a^n-b^n,a^m-b^m)=a^{(n,m)}-b^{(n,m)}
·若 n^a \equiv 1 \pmod{m} 且 n^b \equiv 1 \pmod{m} ，则 n^{(a,b)} \equiv 1 \pmod{m}
请读者自行意会证明，这里不加赘述。
裴蜀定理
裴蜀定理(Bézout's lemma)，又称贝祖定理，是不定方程问题的重要定理，可用于判断不定方程是否有整数解。
内容
形如 $ax+by=c$ 的不定方程有解的**充分必要**条件是 $c\mid(a,b)$。
## 证明
这里给出一种简单的证法。
首先要明确 $\forall x \in \mathbb{Z},x \mid 0$。
### 充分性证明
命题给出的整数 **$a,b$ 不都为 $0$**，所以我们假设 $a \neq 0$。
构造集合 $S=\{ax+by:x,y\in \mathbb{Z},ax+by>0\}$。
$\therefore S \subset \mathbb{N}$，且 $S$ 不为空集。
根据良序公理可得：集合 $S$ 里必定存在最小正元素 $d=ax+by$。
假设 $d \nmid a$，那么存在$k\in \mathbb{Z},r \in \mathbb{N}$ 使得 $a=kd+r,r<d$。
将 $d=ax+by$ 代入得：
$$r=a(1-kx)+b(-ky)$$
又 $\because d$ 为集合 $S$ 的最小正元素
$\therefore r=0,d \mid a
同理可证 d \mid b 。
所以 d 是 a,b 的公约数。
设 div 为 a,b 的一个公约数，即 div \mid a,div \mid b 。
\Rightarrow div \mid ax+by
等价于 div \mid d,div \leq d 。
所以 \forall x \mid a,x \mid b 有 x \mid d,x \leq d 。
\therefore d=(a,b)
所以线性组合 ax+by 的最小正整数解为 (a,b) 。
证毕。
### 必要性证明
设 $d=(a,b)$，则：
$$d \mid a,d \mid b$$
$$\Rightarrow d \mid ax,d \mid by$$
$$\Rightarrow d \mid ax+by$$
$$\texttt{证毕}$$
## 裴蜀定理的推论
同理可证：$x,y \in \mathbb{Z}$，不定方程 $x_1y_1+x_2y_2+\dots+x_ny_n=z$ 有解的**充分必要**条件为 $\gcd_{i=1}^{n}y_i \mid z$。
下面看一下板子题。
## [P4549 【模板】裴蜀定理](https://www.luogu.com.cn/problem/P4549)
### 分析
求不定方程的最小正整数解，只需求系数的 gcd 即可。
### AC CODE
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,x,ans;
int main(){
cin>>n;
cin>>ans;
for(int i=2;i<=n;i++){
cin>>x;
ans=__gcd(ans,abs(x));
}
cout<<ans;
return 0;
}
```
# 扩展欧几里得算法(exgcd)
上文的裴蜀定理已经能够帮助我们判断某一不定方程是否有整数解，而如果我们知道某一不定方程的一特解就能够很容易地得出其通解，可是该怎样求这一组特解呢？
**扩展欧几里得算法**就可以很好地完成这一任务。它可以求出不定方程 $ax+by=(a,b)$ 的**一组特解。**
下面我们来看一下具体实现过程。
$$\because (a,b)=(b,a \bmod b)$$
$$\therefore ax+by=(a,b)=(b,a \bmod b)=bx+(a \bmod b)y$$
递归直到 $b=0$，得 $ax=a$，则此时一组解为：
$$
\begin{equation}
\left\{
\begin{aligned}
x&=1\\
y&=0\\
\end{aligned}
\right.
\end{equation}
$$
假设 $ax+by=(a,b)=bx_0+(a \bmod b)y_0
\because a \bmod b=a-\lfloor\dfrac{a}{b}\rfloor\cdot b
\therefore ax+by=bx_0+(a-\lfloor\dfrac{a}{b}\rfloor\cdot b)y_0
\therefore ax+by=ay_0+b(x_0-\lfloor\dfrac{a}{b}\rfloor\cdot y_0)
\begin{equation}
\therefore
\left\{
\begin{aligned}
x&=y_0\\
y&=x_0-\lfloor\dfrac{a}{b}\rfloor\cdot y_0\\
\end{aligned}
\right.
\end{equation}
这样我们就能递归求得一组可行整数解 x_0 ，y_0 。
易得通解为：
\begin{equation}
\left\{
\begin{aligned}
x&=x_0+k \cdot \frac{b}{(a,b)}\\
y&=y_0-k \cdot \frac{a}{(a,b)}\\
\end{aligned}
\right.
\end{equation}
令 T=\dfrac{b}{(a,b)} ，则 x 最小正整数解 为：
x=(x_0 \bmod T+T) \bmod T
当然，同理可得 y 的最小正整数解。
而如果等号右边的数 c 不是 gcd(a,b) ，则最小非负解 x=(x_0\cdot\dfrac{c}{(a,b)} \bmod T+T) \bmod T 。
通过裴蜀定理 得到一个显然的结论：若 (a,b) \nmid c ，原不定方程无整数解 。
code
int exgcd(int a,int b){
if(b==0){
x=1,y=0;
return a;
}
int gcd=exgcd(b,a%b);
int t=x;
x=y;
y=t-a/b*y;
return gcd;
}基于值域预处理的快速 gcd
作者还没来得及写，应该会在 2024.8.31 前写完。 qaq
数论四大定理
还没开始写…随便搭了点框架……
威尔逊定理
内容
(p-1)! \equiv
证明
费马小定理
内容
证明
欧拉函数
欧拉定理
内容
证明
扩展欧拉定理
内容
证明
扩展欧拉定理降幂应用
中国剩余定理(CRT)
内容
证明
扩展中国剩余定理(EXCRT)
内容
证明
筛法
何为筛法，其实答案就藏在这两个字里。十分形象地说，从某个范围的数中，通过一定的方法进行筛选以得到结果的方法就叫筛法。
素数筛法
顾名思义，筛选素数的算法。在算法竞赛中，由于素数的许多特殊性质，我们常常需要预处理出某个范围内的素数，所以素数筛法的应用十分广泛。
埃氏筛
埃氏筛，全称埃拉托尼斯特尼筛法(sieve of Eratosthenes) ，思想是素数的 x 倍(x \geq 2 )都是合数 ，而合数的 x 倍(x \geq 2 )都不是质数，所以标记 \sqrt{n} 以内c 必有一个 \sqrt{c} 以内的质因子)的所有筛选范围内的倍数未被标记的即为素数。
时间复杂度 O(n \log n) 。
欧拉筛（线性筛）
欧拉筛，又称线性筛。顾名思义，能够做到线性时间复杂度。
思想
考虑在埃氏筛的基础上进行优化。我们发现，在埃氏筛中，一个合数会被它的至少一半的质因子都标记一遍，欧拉的想法就是让每个合数只被其最小的质因子标记一次 。
实现方法
首先从 2 开始遍历，未被标记的数即为素数，将其加入素数表中；然后从小到大遍历素数表，将当前遍历的数与素数表中的数的积标记（注意到，如果只是这样，仅仅是变了幅面孔的埃氏筛）；接下来，欧拉筛的精髓就来了：如果当前遍历的数被遍历到的素数整除，那么将此数与该素数乘积标记后，就不再用当前数与后面的素数作积标记。
为什么呢？假设我们遍历到 i ，并且遍历素数表中素数 p_j 时有 p_j \mid i ，则对于 p_{j+1} 与 i 的乘积，其最小质因子为 p_j ，能被 p_j \times (\dfrac{i}{p_{j}} \times p_{j+1}) 标记，而 p_j<p_{j+1} ，所以 \dfrac{i}{p_{j}} \times p_{j+1}>i ，一定能在后面遍历到 i+k=\dfrac{i}{p_{j}} \times p_{j+1},k>0 时标记 p_j \times (i+k) ，而 i+k<p_j \times (i+k) ，所以不会存在“漏网”而未被标记的合数。
时间复杂度分析
注意到，里面虽然是两层循环，但每个数只会被遍历一次，且合数会被额外标记一次 ，所以时间复杂度是线性的。
code of P3383 【模板】线性筛素数
bool vis[100000005];
int n,q,prime[6000005],k;
void ola(int n){
vis[1]=1;
for(int i=2;i<=n+2;i++){
if(!vis[i]){
prime[++k]=i;
}
for(int j=1;j<=k&&i*prime[j]<=n+2;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0){
break;
}
}
}
}筛法里面还有几个二级标题没写……
Miller Rabin 素性检测
原理
实现
模板题？模板题！
提示：本题不可以尝试要用 Miller Rabin 算法实现 。Miller Rabin 算法是本题具有正确性的乱搞解法。
模意义下的乘法逆元
what is 模意义下的乘法逆元？
It's Modular Multiplicative Inverse.
线性同余方程 ax \equiv 1 \pmod b 的解称为 a 模 b 意义下的乘法逆元a^{-1} 。
用途
当我们进行带取模的 四则运算时，加减乘在取模之后不受影响，但是除法显然是不对的，此时求 (res \div a) \bmod b 的运算结果应当计算 (res \times a^{-1}) \bmod b 。
求乘法逆元
方法很多，各有优劣，我们挨个来看。
一个整数一定存在乘法逆元吗
摘要：不一定。
### 费马小定理求逆元
注意到费马小定理中 $a^{p-1} \equiv 1 \pmod p$ 即 $a \cdot a^{p-2} \equiv 1 \pmod p$，所以 $a$ 在模 $p$ 意义下的乘法逆元为 $a^{p-2}$。
快速幂求解即可。
注意，这里的 $p$ 不得不为质数。
### 扩展欧几里得算法(exgcd)求逆元
观察不定方程 $ax+by=1$ 。
两边同时模 $b$ 得：
$$ax \bmod b=1 \bmod b$$
$$\Rightarrow ax \equiv 1 \pmod b$$
所以该不定方程里的 $x$ 即为 $a$ 模 $b$ 意义下的逆元。
当然可以用 **exgcd** 求啦，有解的充要条件为 $(a,b)=1$。
这就是 [P1082 [NOIP2012 提高组] 同余方程](https://www.luogu.com.cn/problem/P1082)，这里贴一下代码吧。
#### AC CODE
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c,x,y,m,n,L;
int exgcd(int a,int b){
if(b==0){
x=1,y=0;
return a;
}
int gcd=exgcd(b,a%b);
int t=x;
x=y;
y=t-a/b*y;
return gcd;
}
signed main(){
cin>>a>>b;
int GCD=exgcd(a,b);
int T=b/GCD;
cout<<(x%T+T)%T<<"\n";
return 0;
}
```
~~`#define int long long` 是写着玩的，读者请自行开 `long long` qaq。~~
### 线性求$[1,n]$的逆元
首先 $1 \times 1 \equiv 1 \pmod p$，所以 $1$ 的乘法逆元是 $1$。
然后 $p$ 可以表示为 $\lfloor\dfrac{p}{i}\rfloor \cdot i+(p \bmod i),i \in [1,+\infty)$。
$$\therefore \lfloor\dfrac{p}{i}\rfloor \cdot i+(p \bmod i) \equiv 0 \pmod p$$
将左右同时乘 $i^{-1} \times (p \bmod i)^{-1}$ 得：
$$\lfloor\dfrac{p}{i}\rfloor \cdot (p \bmod i)^{-1}+i^{-1} \equiv 0 \pmod p$$
$$\Rightarrow i^{-1} \equiv -\lfloor\dfrac{p}{i}\rfloor \cdot (p \bmod i)^{-1} \pmod p$$
这样就可以**线性**求出 $[1,n]$ 的逆元了,为保证逆元非负，每个数的逆元直接**加上模数 $p$** 即可。
#### code
```cpp
inv[1]=1;
for(int i=2;i<=n;i++){
inv[i]=p-(p/i)*inv[p%i]%p;
}
```
这便是模板题[P3811 【模板】模意义下的乘法逆元](https://www.luogu.com.cn/problem/P3811)。
同时当然有 $a \times b \times a^{-1} \times b^{-1} \equiv 1 \pmod p$，所以 $ab^{-1}=a^{-1} \cdot b^{-1}$，当然可以结合欧拉筛啦，对质数用公式求，对合数用两因数的逆元之积求（搞怪做法，请勿参考）。
#### code
```cpp
#include<bits/stdc++.h>
using namespace std;
long long n,p;
int inv[3000005],vis[3000005],prime[10005],cnt;
void solve(){
inv[1]=vis[1]=1;
cout<<1<<"\n";
for(int i=2;i<=n;i++){
if(!vis[i]){
prime[++cnt]=i;
inv[i]=(p-p/i)*inv[p%i]%p;
}
for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
vis[i*prime[j]]=1;
inv[i*prime[j]]=inv[i]*1ll*inv[prime[j]]%p;
if(!(i%prime[j])){
break;
}
}
cout<<inv[i]<<"\n";
}
}
int main(){
cin>>n>>p;
solve();
return 0;
}
```
### 线性求任意 $n$ 个数的逆元
#### 思路
先求出序列前 $i$ 个数的**前缀积** $s_i$。即可通过费马小定理或 exgcd 求出 $s_{n}^{-1}$。再求出**每个前缀积的逆元** $sinv_i=sinv_{i+1} \times a_{i+1}$。再求出**每个数的逆元** $inv_i=sinv_{i} \times s_{i-1}$ 就好啦。
放道模板题~~~。
#### [P5431 【模板】模意义下的乘法逆元 2](https://www.luogu.com.cn/problem/P5431)
只需要再求出乘法逆元后按照题目模拟统计答案即可。
~~但是这题要**卡常**……~~
模数一定是质数，所以用的费马小定理，也可以用 exgcd。
贴一下代码 qaq。
#### AC CODE
```cpp
#include<bits/stdc++.h>
using namespace std;
inline long long read(){
long long x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,a[5000005],s[5000005],inv[5000005],sinv[5000005],M,k;
long long ksm(long long a,long long b,long long p){
long long ans=1;
while(b!=0){
if(b&1){
ans=(ans*a)%p;
}
b>>=1;
a=(a*a)%p;
}
return ans;
}
int main(){
n=read();
M=read();
k=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
s[0]=1;
for(int i=1;i<=n;i++){
s[i]=((long long)a[i]*s[i-1])%M;
}
sinv[n]=ksm(s[n],M-2,M);
for(int i=n;i>=1;i--){
sinv[i-1]=(long long)sinv[i]*a[i]%M;
}
for(int i=1;i<=n;i++){
inv[i]=(long long)sinv[i]*s[i-1]%M;
}
long long ans=0,tmp=k;
for(int i=1;i<=n;i++){
ans=(ans+tmp*inv[i]%M)%M;
tmp=tmp*k%M;
}
printf("%lld\n",ans%M);
return 0;
}
```
### 求阶乘逆元
# 线性同余方程
又是没写的一块，估计会在数论四大定理之后写……
后面 の 一级标题还差一大截……
本 Blog 正在编写中，未完待续……
# 参考资料：
[OI Wiki-数学-数论](https://oi.wiki/math/)
[worldream の 知乎数论系列](https://zhuanlan.zhihu.com/p/611670099)