\[\large\text{本以为学的是数学专题，实际上学的是} \]\[\huge\stackrel{\text{xuán}}{\textbf{数}}\textbf{学专题} \]
玄学专题
\(\Huge\textbf{1}\ \small\text{Exgcd(扩展欧几里得)}\)
\[\boxed{gcd(a,b)\le ax+by}。 \]Exgcd 能够在 \(\Theta\small (\text{log}_n)\) 的时间复杂度中求出满足方程 \(ax+by=\gcd(a,b)\) 的解。可以证明一定有解。
\(\text{正确性证明}\)
（自己太菜不会证 摘自网上博客）
若 \(\gcd(b,a\,\text{mod}\,b)=bx_0+(a\,\text{mod}\,b)y_0\)，则有
\(\gcd(b,a\,\text{mod}\,b)=bx_0+(a-\lfloor\frac{a}{b}\rfloor b)y_0\)。
整理得 \(\gcd(b,a\,\text{mod}\,b)=ay_0+(x_0-\lfloor\frac{a}{b}\rfloor)by_0\)。
根据辗转相除，\(\gcd(b,a\,\text{mod}\,b)=\gcd(a,b)\)，有 \(\gcd(a,b)=ay_0+(x_0-\lfloor\frac{a}{b}\rfloor)by_0\)。
由定义，\(\gcd(a,b)=ax+by\)。所以 \(x=y_0,y=(x_0-\lfloor\frac{a}{b}\rfloor)y_0\)。
int Exgcd(int a,int b,int &x,int &y){
if(b){
int la=Exgcd(b,a%b,x,y),mem=x;
x=y;
y=mem-(a/b)*y;
return la;
}
x=1,y=0;
return a;
}
该函数的返回值为 \(\gcd(a,b)\)，\(x\) 和 \(y\) 的值为方程的解。
\(\Huge\textbf{2}\ \small\text{费马小定理}\)
如果 \(k\) 是质数，那么 \(a^{k-1}\equiv 1\pmod{k}\)。
\(\Huge\textbf{3}\ \small\text{乘法逆元}\)
如果 \(ax\equiv 1\pmod{p}\)，且\(\mathbf{\gcd(a,p)=1}\)，则称 \(a\) 关于 \(p\) 的乘法逆元为 \(x\)。
模板题 [P1082 同余方程]
把上面的式子稍微变形得到 \(ax\equiv \gcd(a,p)\pmod{p}\)，即 \(ax+py=\gcd(a,p)\)。就成功地把锅甩给了转化为 Exgcd。
逆元有什么用？
答：乘法逆元，大大的好用！
以下均用 \(inv(x)\) 表示 \(x\) 的乘法逆元。
\(\Large\textbf{1}\ \small\text{化除为乘}\)
求\(\frac{a}{b}\,\text{mod}\,p\)。
首先，\(\frac{a}{b}\,\text{mod}\,p \not= \frac{a\,\text{mod}\,p}{b\,\text{mod}\,p}\)。
但是，\(\frac{a}{b}\,\text{mod}\,p = a·inv(b)\,\text{mod}\,p\)。
这个性质在求组合数问题中被广泛应用。
说句闲话，研究同余方程的最好方式是……
使用费马小定理！
上述式子还可以转化为 \(a·b^{p-2}\,\text{mod}\,p\)。
\(\Huge\textbf{4}\ \small\text{CRT(中国剩余定理)}\)
（摘自我自己）若有
\(\begin{cases}x\equiv a_1&(\mod b_1)\\x\equiv a_2&(\mod b_2)\\...\\x\equiv a_n&(\mod b_n)\\\end{cases},\)
则有\(M=\prod^n_{i=1}b_i,M_i=\frac{M}{b_i},t_i=inv(M_i)\text{mod}\,b_i.\)
则
证明显然。
\(\Huge\textbf{5}\ \small\varphi\text{(Euler函数)}\)
\(\varphi(k)\) 表示 \(\sum_{i=1}^k [\gcd(i,k)=1]\)。说人话就是 \(1-k\) 中与 \(k\) 互素的数的个数。
朴素做法求Euler函数：\(\varphi(k)=\prod_{i=1}^k[i|k\land i\text{为素数}]\times log_ik\)
翻译成人话就是：如果 \(k=a_1^{q_1}a_2^{q_2}a_3^{q_3}a_4^{q_4}\dots a_n^{q_n}\)，则 \(\varphi(k)=k·\prod_{i=1}^n\frac{q_i-1}{q_i}\)。
筛法求Euler函数：
int getphi(int t__){//t__为上限。
phi[1]=1;//显然。
for(int i=2;i<=t__;i++){
if(st[i]==0){//如果该数是质数的话，phi(该数)=该数-1。
pr[++top]=i;
phi[i]=i-1;
}
for(int j=1;pr[j]*i<=t__;j++){//开始筛
st[pr[j]*i]=1;//显然pr[j]*i不是质数。
if(i%pr[j]==0){//筛法特性
phi[i*pr[j]]=phi[i]*pr[j];
break;
}
phi[i*pr[j]]=phi[i]*(pr[j]-1);
}
}
}
\(\Huge\textbf{6}\ \small\text{组合数}\)
定义 \(C_j^i\) 为将 \(j\) 个不同的球放入 \(i\) 个不同的盒子里的方案数。
\(C_j^i=\frac{j!}{(j-i)!i!}\)。
小推论：\(C_j^i=C_j^{i-1}+C_{j-1}^{i-1}\)。
可以用乘法逆元优化阶乘相除的计算，使得某种算法可以求出 \(1\times 10^5\) 大小的组合数（取膜后）。
\(\Huge\textbf{7}\ \small\text{卡特兰数（明安图数）}\)
卡特兰数的第 \(n\) 项等于 \(\frac{C_{2n}^{n}}{n+1}\) 或 \(\frac{4n-2}{n+1}Catalan(n-1)\) 。
标签：frac,gcd,text,Exgcd,textbf,small,浅谈,同余,mod From： https://www.cnblogs.com/lunatic-unleashed/p/oh.html