exgcd & 线性同余方程

前置芝士

裴蜀定理
同余的性质

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 = exgcd(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\)求解即可

巴特西

exgcd & 线性同余方程

前置芝士

exgcd

推导过程：

同余方程

最新文章

热门文章