数论基础
前言：
一些比较基础的数论知识
正文：
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;//保证逆元为正数
第二种求法是费马小定理
如果 $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;
第三种求法是欧拉定理
同样的，如果 $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:$ 数学真是有趣呐~~~
转载于
//www.cnblogs.com/Vscoder/p/10551356.html
朴灿烈づ我的快乐病毒、
爱被打了一巴掌
还没有评论，来说两句吧...