♠ use C++11
最大公约数
-
若 \(a,b\in \mathbb N\) 且 \(k \mid a,b \in \mathbb N\)，且不存在更大的 \(k\)，称 \(k\) 是 \(a,b\) 的最大公约数。
-
快速求 \(a,b\in \mathbb N\) 的最大公约数，欧几里得定理：\(\gcd(a,b)=\gcd(b,a \bmod b)\)。
-
已知 \(a,b \in \mathbb N\)，可找到 \(x,y \in \mathbb Z\) 使 \(a\times x +b\times y=\gcd(a,b)\)，若 \(a\times x+b\times y=1\) 有解，则 \(a\) 和 \(b\) 互质。
-
扩展欧几里得，一定存在 \(x,y\in \mathbb N\) 使贝祖等式 \(a\times x +b\times y=\gcd(a,b)\)\(\Rightarrow (\left \lfloor a \div b \right \rfloor \times b + a \bmod b) \times x + b\times y = \gcd(b,a\bmod b)\)\(\Rightarrow (\left \lfloor a \div b \right \rfloor \times x + y)\times b +(a \bmod b)\times x\)，可得新的方程 \(b \times x'+(a \bmod b)\times y' = \gcd(b,a\bmod b)\) 因此可得 \(\begin{cases}x'=(\left \lfloor a \div b \right \rfloor\times x+y)\\y'=x\end{cases}\)，同样倒推可得特解 \(\begin{cases}x=y'\\y=x'-(\left \lfloor a \div b \right \rfloor\times y')\end{cases}\)，下面是递归代码实现。
#include<array>
array<long long,3> exgcd(long long a,long long b){
if(b==0) return {1,0,a};
//当b=0时，等式为ax=gcd(a,0)，即ax=a
//得x=1,y=0
array<long long,3> ans=exgcd(b,a%b);
long long temp=ans[0];
ans[0]=ans[1];
ans[1]=temp-a/b*ans[1];
return ans;//ans[0]为x，ans[1]为y，ans[2]为gcd(a,b)
}
- 当求得贝祖等式特解 \(x_0,y_0\in \mathbb N\) 后，可得 \(x,y\in \mathbb N\) 通解，设 \(g=\gcd(a,b)\) 通解为 \(\begin{cases}x=x_0+t\times b\div g\\y = y_0- t \times a \div g\end{cases}\)，推导过程：\(\begin{cases}a\times x+b\times y=g\\a\times x_0+b\times x_0=g\end{cases}\)\(\Rightarrow (x-x_0)\times a+(y-y_0)\times b=0\)\(\Rightarrow (x-x_0)\times a=(y_0-y)\times b\)\(\Rightarrow (x-x_0)\times \dfrac{a}{g}=(y_0-y)\times \dfrac{b}{g}\)\(\Rightarrow \begin{cases}x-x_0=t\times \dfrac{b}{g}\\y_0-y=t \times \dfrac{a}{g}\end{cases}\)\(\Rightarrow \begin{cases} x=x_0+t\times\dfrac{b}{g}\\y=y_0-t\times\dfrac{a}{g}\end{cases}\)，其中 \(x\) 的第一个解是 \(\bigg(x\bmod\dfrac{b}{g}+\dfrac{b}{g}\bigg)\bmod \dfrac{b}{g}\)。
模运算
-
已知 \(a,b,p\in \mathbb N\)，\((a+b)\bmod p=(a\bmod p+b\bmod p)\bmod p\)，\((a-b)\bmod p=(a\bmod p+b\bmod p)\bmod p\)，\((a\times b)\bmod p=(a \bmod p\times b\bmod p)\bmod p\)。
-
若需要进行除法的模运算，与普通的不同，例子：\(\dfrac{20}{10}\bmod 5 \neq \dfrac{20 \bmod 5}{10\bmod 5}\bmod 5\)，所以为了求 \((a\div b) \bmod p\)，\(a,b,p\in\mathbb N\)，需要找到 \(b\) 的乘法逆元 \(x\in\mathbb N\)，将算式变成 \((a\times x)\bmod p\)。
-
已知 \(a,x,m\in \mathbb N\)，\(ax \equiv 1\pmod p\)\(\Rightarrow ax \bmod p=1\)\(\Rightarrow ax-\left\lfloor\dfrac{ax}{p}\right\rfloor\times p=1\)，称 \(x\) 是关于 \(a\) 的乘法逆元，将 \(-\left\lfloor\dfrac{ax}{p}\right\rfloor\) 用 \(y\) 替代，得 \(ax+py=1\)，即找到 \(x\) 的值即可找到 \(a\) 的乘法逆元，也可知 \(a,p\) 必须要互质。