前置芝士
- 裴蜀定理
exgcd
exgcd即扩展欧几里得定理，常用来求解\(ax + by = gcd(a,b)\)的可行解问题
推导过程：
考虑我们有：
\(ax + by = gcd(a,b)\)——裴蜀定理
\(a_1x_1 + b_1y_1 = gcd(a_1,b_1)\)
当我们从\(1\)到\(2\)时，即\(gcd(a_1,b_1)\rightarrow gcd(a_2,b_2) = gcd(b_1,b_1\%a_1)\)
\(a_2x_2+ b_2y_2 = gcd(a2,b2)\Rightarrow b_1x_2 + (b_1\%a_1) y_2 = gcd(b_1,b_1\%a_1)\)
直到\(gcd(a_n,b_n)\ \ b_n = 0\)
\(a_nx_n+b_ny_n = gcd(a_n,b_n)\Rightarrow a_nx_n + 0 * y_n = gcd(a_n,0) = a_n\)
此时我们看出，\(x_n = 1，y_n = 0\)（\(y_n\)其实可以取任意一个数）时是一组特殊解
现在我们考虑怎么从\(n\rightarrow1\)推出我们需要的一组\(x,y\)
从上面给出的例子，我们可以推出：
\(\because gcd(a,b) = gcd(b,a\%b)\)
\(\therefore a_1x_1 + b_1y_1 = b_1x_2 + (b_1-\lfloor\frac{b_1}{a_1}\rfloor\times a_1)y_2 = a_1y_2 + b_1(x_2-\lfloor\frac{a}{b}\rfloor y_2)\)
然后我们可以推出：
\(\begin{cases}x_i = y_{i+1} \\ y_i = x_{i+1}+\lfloor\frac{a_i}{b_i}\rfloor y_{i+1}\end{cases}\)
solved!
下面附代码：
int exgcd(int a,int b,int &x,int &y){
if(!b){x = 1;y = 0;return a;}
int d = edgcd(b,a%b,x,y);
int t = x;
x = y;
y = t - (a/b) * y;
return d;
}
同余方程
形如\(ax\equiv b(mod\ n)\)的方程称为同余方程，其中\(a,b,n\)给出，求出\(x\)
我们按上面的方程可以化出这个式子\(ax+nk = b\)
用\(exgcd\)求解即可
标签：gcd,int,1x,exgcd,线性,ax,同余 From： https://www.cnblogs.com/rickylin/p/17053687.html