数论（待进阶）

1.欧几里德算法

作用：对于给定的a,b，求a,b的最大公约数gcd(a,b)

要求：无

证明：我们先想证明\(gcd(a,b)=gcd(b,a\%b)\)

我们先证明\(gcd(a,b)=gcd(a-xb)\)

这样，当\(x=1\)时，他就是辗转相除法\(gcd(a,b)=gcd(b,a-b)\)

当\(x=\frac{a}{b}\)，且除法向下取整，则此时\(gcd(a,b)=gcd(b,a\%b)\)

所以只要证明出来\(gcd(a,b)=gcd(a-xb)\)对于任意的\(x\)成立，我们就可以证明欧几里德算法成立

真正的证明

设\(gcd(a,b)=c,gcd(b,a-xb)=d\)

根据性质，可以写出

\(\because c|a,c|b\)

\(\therefore c|(a-xb)\)

\(\therefore c|gcd(b,a-xb)\Leftrightarrow c|d\)

\(\because d|b \therefore d|(xb)\)

又\(\because d|(a-xb) \ \therefore d|a\)

\(\therefore d|gcd(a,b)\Leftrightarrow d|c\)

\(\because d|c\ \&\ c|d\)

\(\therefore c==d\)

所以，我们可以证明欧几里德算法成立

代码：

inline int gcd( int x , int y ){
    return y == 0 ? x : gcd( y , x % y ) ;
}

2.扩展欧几里德

作用：解出来二元一次方程组ax+by=c

要求：c%gcd(a,b)=0

实质上，扩展欧几里德解的是\(a*x+y*b=gcd(x,y)\)，解出来的\(x,y\)是绝对值最小的解，有可能是负数。

那么，对于任意已知\(a,b,c\)的

\[a*x+b*y=c \]

我们都可以通过扩展欧几里德来求解，我们可以考虑先给全部式子都乘上 \(\large\frac{gcd(a,b)}{c}\)

那么，式子就会变成

\[a*\frac{gcd(a,b)}{c}*x+b*\frac{gcd(a,b)}{c}*y=gcd(a,b) \]

这样我们发现其实对于a,b这个式子就是一个扩展欧几里德了，只不过我们解出来的\(x_0,y_0\)分别是\(x_0*\frac{gcd(a,b)}{c},y_0*\frac{gcd(a,b)}{c}\)，我们只需要把求出来的\(x,y\)都乘上\(\frac{c}{gcd(a,b)}\)就可以了

但是我们发现\(\frac{c}{gcd(a,b)}\)是整数当且仅当\(c \% gcd(a,b)==0\)，这也就是上文中要求的由来

但是，我们还可以发现，其实这个方程肯定有无限组解，我们只求出来了一组特殊解，怎么推广到全部呢？

我们可以把\(a*x+b*y\)写成

\[(a*x-a*k*b)+(b*y+a*k*b)\Leftrightarrow a*(x-k*b)+b*(y+k*a) \]

那么，我们求出来的\(x,y\)都可以变成\((x-k*b),(y+k*a)\)

所以现在我们只需要考虑\(k\)的取值范围就行了

但是观察了许久，发现并没有什么范围

于是我们想，如果能让\(k\)取遍他的定义域的同时求出所有解，那么这个\(k\)一定是唯一的，且不能再小，再小就会得到不正确的解，再大就不能得到所有解

我们让\(k\)最小不就行了？

我们发现，我们只需要满足\(k*a\)和\(k*b\)都是整数，其他方面没有对\(k\)有过多要求

所以\(k\)的最小值就得到了，我们得\(k=\frac {1}{gcd(a,b)}*t \ |t\in Z\)

易得t取遍z的时候，所有解集就得到了

所以

对于

\[a*x+b*y=c \]

\[x=x_0*(\frac{c}{gcd(a,b)})-t*\frac{b}{gcd(a,b)} \|t\in Z \]

\[y=y_0*(\frac{c}{gcd(a,b)})+t*\frac{a}{gcd(a,b)} \|t\in Z \]

还有一个事情，就是最小正数解，我们只需要把\(x\)搞成\(((x\%b)+b)\%b\)就可以了，其实也就是\(x<0\)的时候\(x+=\frac{b}{gcd(a,b)}\)

说了这么多，忘记证明扩展欧几里德的原理了

为什么我们可以求出\(x,y\)?

根据欧几里德算法，我们知道
我们还知道，当\(b=0\)时，\(a=gcd\)，算法停止

所以我们可以得到\(a*1+b*0=gcd\)

得到一个状态后，我们只需要得到如何转移状态即可

由于

\[gcd(a,b)=gcd(b,a\%b) \]

又由于\(a\%b==a-(a/b)*b\),这里除法向下取整

我们展开模运算和gcd，可以得到

\[x=y_0,y=x_0-(a/b)*y \]

代码

inline int exgcd( int a , int b , int & x , int & y ){
  if( b == 0 ){
    x = 1 , y = 0 ;
    return a ;  
  } int ans = exgcd( b , a % b , x , y ) ;
  int t = x ; x = y ; y = t - y * ( a / b ) ; 
  return ans ;
}

学会这个东西，有什么用处呢？其实最大的用处是求乘法逆元

3.乘法逆元

用处：解决\(（a/b）\%c \not=((a\%c)/(b\%c)\)的问题

我们知道\(（a/b）\%c \not=((a\%c)/(b\%c)\)，所以，如果\(a/b\)很大的话，我们如何计算呢？

这里就要引入一个乘法逆元,我们可以找到一个数\(x\),使得\(（a/b）\%c =((a\%c)*(x\%c))\%c\)
这个\(x\)就是\(b\)关于\(c\)的乘法逆元
\(x\)的计算方法是\(x*b≡1(mod\ c)\),由于\(b,c\)已知，我们只需要用扩展欧几里德解\(x*b+t*c=1\)
得到一个\(x\)，把\(x\)变成最小正整数解就可以了
在这种计算方法下，要求\(gcd(b,c)\%1=0\),也就是\(gcd(b,c)=1\)

还有一个求法，费马小定理\(x=b^{c-2}\),当\(p\)是质数的时候成立，需要打一个快速幂。

这两种复杂度都是\(log(n)\)，都用于求一个数的乘法逆元，扩欧的要求更少。

如果一道题我们需要求\(1~n\)的乘法逆元，那么我们的复杂度是\(nlog(n)\)，但是其实还有一种更快的方法

证明不太会，以后再说，直接给代码

int inv [N] ;
inv [1] = 1 ;
for( int i = 2 ; i <= n ; i ++ )//i mod p 的逆元 
  inv [i] = ( p - （ p / i ） ) + inv [p % i] % p ;