数论基础

约定不等于承诺〃 2021-12-16 04:36 337阅读 0赞

## 前言： ##

一些比较基础的数论知识

## 正文： ##

### GCD ###

$gcd$ 的求法当然要用欧几里得定理，就是辗转相除

int gcd(int a,int b) { if(!b) return a; return gcd(b,a%b); }

求出了 $gcd$ 之后，我们就可以求出 $lcm$（最小公倍数）

有一个性质是 $gcd(a,b) \\times lcm(a,b)=a \\times b$，这样就可以 $O(1)$ 求出 $lcm$

### EXGCD ###

$exgcd$ 即扩展欧几里得定理

可以用来求解 $ax+by=gcd(a,b)$ 的一组解

具体做法就是辗转相除到底然后回带，详情参见代码

以下是魔改董大佬的写法

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

以下是魔改 $pc$ 大佬的写法

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

### 快速幂 ###

用于指数较大的情况

同时可以一边计算一边取模，防止爆 $long\\ long$

ll qpow(ll a,ll b,ll p) { ll ans=1,base=a%p;//记得先取模
        while(b) { if(b&1) ans=ans*base%p; base=base*base%p; b>>=1; } return ans; }

### 龟速乘 ###

魔改的快速幂，防止直接乘起来会爆 $long\\ long$

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

### 乘法逆元 ###

#### 定义 ####

如果 $ab\\equiv 1\\ (mod\\ p)$ 且 $gcd(a,p)=1$ ，则称 $a$ 在 $mod\\ p$ 意义下的乘法逆元为 $b$

我们知道在取模运算下是不能随便除的，所以我们定义了逆元，$\\dfrac a b\\equiv a\\times inv(b)\\ (mod\\ p)$

化简即可得 $b \\times inv(b)\\equiv 1\\ (mod\\ p)$

#### 求法 ####

关于它的求法，这里介绍三种

我们知道 $a \\times inv(a)\\equiv 1\\ (mod\\ p)$ 且 $gcd(a,p)=1$

所以第一种方法就是刚刚介绍的 $EXGCD$

由逆元的定义我们可以得到 $a \\times inv(a) +k \\times p=1$

而又因为 $gcd(a,p)=1$ ，所以 $a \\times inv(a) +p \\times k=gcd(a,p)$

于是我们就可以直接解出 $a$ 在 $mod\\ p$ 意义下的逆元

exgcd(a,p,inv,k); inv=(inv%p+p)%p;//保证逆元为正数

第二种求法是***[费马小定理][Link 1]***

如果 $p$ 为质数，并且 $gcd(a,p)=1$ ，那么 $a^\{p-1\}\\equiv 1\\ (mod\\ p)$

所以它可以用来解决模数 $p$ 是质数的情况

由 $a^\{p-1\}\\equiv 1\\ (mod\\ p)$ 可知 $a \\times a^\{p-2\}\\equiv 1\\ (mod\\ p)$

所以 $a$ 在 $mod\\ p$ 意义下的逆元即为 $a^\{p-2\}$，快速幂可求

inv=qpow(a,p-2,p)%p;

第三种求法是***[欧拉定理][Link 2]***

同样的，如果 $gcd(a,p)=1$，则有 $a^\{φ(p)\}\\equiv 1\\ (mod\\ p)$

所以它也可以解决模数 $p$ 不是质数的情况

由 $a^\{φ(p)\}\\equiv 1\\ (mod\\ p)$ 可知 $a \\times a^\{φ(p)-1\}\\equiv 1\\ (mod\\ p)$

所以 $a$ 在 $mod\\ p$ 意义下的逆元即为 $a^\{φ(p)-1\}$，快速幂可求

inv=qpow(a,phi[p]-1,p)%p;

#### 线性递推 ####

我们设$a=\\lfloor\\dfrac p i\\rfloor,b=p\\%i$

所以 $a \\times i+b=p$

所以 $a \\times i+b\\equiv 0\\ (mod\\ p)$

所以 $i\\equiv -\\dfrac\{b\}\{a\}\\ (mod\\ p)$

所以 $i^\{-1\}=-a \\times b^\{-1\}$

即 $inv(i)=-(p/i) \\times inv(p\\%i)$

所以我们可以 $O(n)$ 递推

void pre_solve(int n,ll p) { inv[1]=1; for(int i=2;i<=n;i++) inv[i]=inv[p%i]*(p-p/i)%p;//防止逆元为负，我们给它加上一个p
    }

#### 阶乘逆元 ####

在求组合数时，我们还经常需要求阶乘的逆元

根据定义$a! \\times inv(a!)\\equiv 1\\ (mod\\ p)$

所以 $(a-1)! \\times(a \\times inv(a!))\\equiv 1\\ (mod\\ p)$

所以 $inv((a-1)!)=a \\times inv(a!)$

所以我们可以先求出 $inv(a!)$

然后 $O(n)$ 递推出其它阶乘逆元

ll jc[maxn]; ll inv[maxn]; void pre_solve(int n,ll p) { jc[0]=1; for(int i=1;i<=n;i++) jc[i]=(jc[i-1]*i)%p; inv[n]=qpow(jc[n],p-2,p); for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%p; }

## 后序： ##

如果有错误的地方欢迎指正

$ps:$ 数学真是有趣呐~~~

转载于:https://www.cnblogs.com/Vscoder/p/10551356.html

[Link 1]: https://baike.baidu.com/item/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86/4776158?fr=aladdin
[Link 2]: https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86