省选-数学-前置 · Zhl2010 第二博客

exgcd

求整数 $x, y$ 使得 $ax + by = \gcd(a, b)$ 。

已知 $bx' + (a \bmod b)y' = \gcd(b, a\bmod b)$ ，而 $a \bmod b = a - \lfloor a/b \rfloor b$ ，代入得：

bx' + (a - \lfloor a/b \rfloor b)y' = a y' + b(x' - \lfloor a/b \rfloor y')

因此原方程的解为：

x = y', \quad y = x' - \lfloor a/b \rfloor y'

边界：当 $b=0$ 时， $\gcd(a,0)=a$ ，取 $x=1, y=0$ 。

流程：

得到一组整数解（可能为负）。

C++

void exgcd(int a,int b,int &x,int &y){
	if(!b){
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-a/b*y;
}

可以用来求逆元（ $ax\equiv 1\pmod m$ → $ax+my=1$ ，取 $x \bmod m$ ）、解线性同余方程。

模数两两互质。

\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \quad \vdots \\ x \equiv a_n \pmod{m_n} \end{cases}

设 $M=m_1m_2\cdots m_n$ ， $M_i=\frac{M}{m_i}$ ， $t_i=M_i^{-1}$ 。

我们构造：

x=\sum_{i=1}^n a_iM_it_i

我们发现对于每一个 $i$ ，只有在对应的那一位 $a_iM_it_i\mod m_i$ 才不为 $0$ ，而且在 $i$ 的时候答案为 $a_i$ 。

我们需要证明 $M$ 以内没有其他解。

反证法，设 $y$ 也是一个解。

一定有：

x-y≡0\pmod {a_i}\\ M|(x-y)

所以 $M$ 以内只有一个解。

我们发现 $a$ 不再互质了，于是需要换一种思路。我们考虑两两合并。

\begin{cases} x \equiv r_1 \pmod{m_1} \\ x \equiv r_2 \pmod{m_2} \end{cases}

x = k_1 m_1 + r_1 = k_2 m_2 + r_2\\ k_1m_1-k_2m_2=r_2-r_1

我们发现这个可以用 exgcd 求出来。

有解条件： $d=\gcd(m_1,m_2)$ ：

k_1p_1-k_2p_2=\frac{r_2-r_1}{d}

需要 $d|(r_2-r_1)$ 。

用 exgcd 求：

\lambda_1 p_1 + \lambda_2 p_2 = 1

k_1 = \frac{r_2 - r_1}{d} \cdot \lambda_1,\quad k_2 = -\frac{r_2 - r_1}{d} \cdot \lambda_2

x^* = r_1 + k_1 m_1 = r_1 + \frac{r_2 - r_1}{d} \lambda_1 m_1\pmod {lcm(m_1,m_2)}

错排问题 $d_i=(i-1)*(d_{i-1}+d_{i-2})$ 。