最近数论讲的比较多，蒟蒻表示完全懵逼。。。
本来想写篇莫比乌斯反演的，但是懒得搞那么多公式，所以挑篇简单的欧几里得来写，不过类欧几里得算法也是很难的(凉凉。。)所以降低一点难度，写篇基础的。
正题：
注：#define long long LL
欧几里得算法：
很简单的东西，等于辗转相除法，非常简单，贴个代码：
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
扩展欧几里得算法：
是用来解下面的二元方程的：
ax+by=gcd(a,b)ax+by=\mathrm{gcd(a,b)}ax+by=gcd(a,b)
首先我们需要知道两个式子：
a=amodb+⌊ab⌋∗ba=a\;mod\;b+\lfloor\frac{a}{b}\rfloor*ba=amodb+⌊ba⌋∗b
gcd(a,b)=gcd(b,amodb)\mathrm{gcd(a,b)}=\mathrm{gcd(b,a\;mod\;b)}gcd(a,b)=gcd(b,amodb)
上面两个式子显然是对的，就不给证明了。
代入原式可得：
x∗(amodb+⌊ab⌋∗b)+by=gcd(b,amodb)x*(a\;mod\;b+\lfloor\frac{a}{b}\rfloor*b)+by=\mathrm{gcd(b,a\;mod\;b)}x∗(amodb+⌊ba⌋∗b)+by=gcd(b,amodb)
展开括号，提公因式b
(amodb)x+b(⌊ab⌋x+y)=gcd(b,amodb)(a\;mod\;b)x+b(\lfloor\frac{a}{b}\rfloor x +y)=\mathrm{gcd(b,a\;mod\;b)}(amodb)x+b(⌊ba⌋x+y)=gcd(b,amodb)
对照一下这个式子和原式：
ax+by=gcd(a,b)a\;\;\;\;\;\;x\qquad\;\;\;\;+\qquad b\;\;\;\;\;\; y\;=\mathrm{gcd(a,\;\;\;\;\;b)}ax+by=gcd(a,b)
b(⌊ab⌋x+y)+(amodb)x=gcd(b,amodb)b(\lfloor\frac{a}{b}\rfloor x +y)+(a\;mod\;b)x=\mathrm{gcd(b,a\;mod\;b)}b(⌊ba⌋x+y)+(amodb)x=gcd(b,amodb)
不难发现两个式子的形式是一样的，有如下替换关系：
aaa→\rightarrow→bbb
bbb→\rightarrow→amodba\;mod\;bamodb
xxx→\rightarrow→⌊ab⌋x+y\lfloor\frac{a}{b}\rfloor x +y⌊ba⌋x+y
yyy→\rightarrow→xxx
于是我们就可以递归求解这个方程，设该函数为exgcd(a,b,x,y)，那么递归到下一层的参数就是exgcd(b,a%b,y,x)(因为x、y都为未知数，所以我们递归时只改变位置即可)。
递归到最底层时，我们式子的形式依然是这样的：
ax+by=gcd(a,b)ax+by=\mathrm{gcd(a,b)}ax+by=gcd(a,b)
由于在递归时，显然a、b一直在做辗转相除，那么最终a会变成gcd，而b会变成0。所以，对于上面的式子x有唯一解x=1，y可以为任意值。一般情况下，题目会要求求最小正整数解，所以我们返回的值就是x=1，y=0。
返回过程中，我们要更改解的值，根据我们推出的两个变换式：
ax+by=gcd(a,b)ax+by=\mathrm{gcd(a,b)}ax+by=gcd(a,b)
b(⌊ab⌋x+y)+(amodb)x=gcd(b,amodb)b(\lfloor\frac{a}{b}\rfloor x +y)+(a\;mod\;b)x=\mathrm{gcd(b,a\;mod\;b)}b(⌊ba⌋x+y)+(amodb)x=gcd(b,amodb)
可以得到 ：y=y−⌊ab⌋xy=y-\lfloor\frac{a}{b}\rfloor xy=y−⌊ba⌋x
而我们传参的时候已经改变了x、y的位置，所以返回的时候不用管。
代码如下：
LL exgcd(LL a,LL b,LL &x,LL &y){b?(exgcd(b,a%b,y,x),y-=a/b*x):(x=1,y=0);}
