同余方程-526互联

前置知识：

裴蜀定理
扩展欧几里得算法 ( exgcd )

裴蜀定理：

定义：裴蜀定理，又称贝祖定理，是一个关于 $gcd$ 的定理。
内容：设 $a,b$ 整数，则存在整数，使得 $ax+by=\gcd(a,b)$
证明：略。

扩展欧几里得算法 ( exgcd )：

意义：扩展欧几里得算法是用来解决形如 $ax+bd=k$ 的不定方程的一组解。
推导：

由裴蜀定理得：$ax+by=\gcd(a,b)$,
化简得：$ax+by=\gcd(b,a\mod b)$,
构造方程：$bx_0+(a\mod b)y_0=\gcd(b,a\mod b)$,
由模运算的定义，有：$a\mod b=a-\left\lfloor\dfrac{a}{b}\right\rfloor*b$,
因此，原方程化简为：$bx_0+(a-\left\lfloor\dfrac{a}{b}\right\rfloor*b)y_0=\gcd(b,a\mod b)$,
联立方程，得：

$ \left\{ \begin{array}{lc} ax+by=\gcd(b,a\mod b) \\ (a-\left\lfloor\dfrac{a}{b}\right\rfloor*b)y_0+bx_0=\gcd(b,a\mod b) \\ \end{array} \right. $

根据对应系数相等，得：
$ \left\{ \begin{array}{lc} x=(a-\left\lfloor\dfrac{a}{b}\right\rfloor*b)y_0 \\ y=x_0 \\ \end{array} \right. $

Code:

void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
      if(a==0){d=b;x=0;y=1;}
      else
      {
          LL tx,ty;exgcd(b%a,a,d,tx,ty);
          x=ty-(b/a)*tx;y=tx;
      }
}
int main()
{
    	LL a,b,d,x,y,k;
    	scanf("%lld%lld%lld",&a,&b,&k);
    	exgcd(a,b,d,x,y);
    	if(k%d!=0)return 0;
    	x=(k/d)*x;
    	y=(k-a*x)/b;
    	printf("%lld %lld",x,y);
    	return 0;
}

线性同余方程：

定义：形如 $ax\equiv k\pmod{b}$ 的方程叫做线性同余方程。其中，$\equiv$ 是恒等于的意思，而整个方程意思是：
$ \left\{ \begin{array}{lc} ax \pmod b=k \\ k \pmod b=k \\ \end{array} \right. $
解法：解决线性同余方程问题用到的是 $exgcd$ 算法。

由模运算的定义，有：$ax=k-y*b \pmod b $
移项得：$ax+by=k \pmod b$
最后，使用 $exgcd$ 得到 $x$ 的解。

最小正整数解：因为不定方程的解有很多种，出题人不喜欢打 $spj$ ,所以题目一般会求最小正整数解。在方程：$3x+4y=21$ 中，根据数学直觉，我们可以得到一组解 $x=7,y=0$ ，这组解是最小正整数解吗，显然不是。因为我们根据数学直觉，可以得到另一组解 $x=3,y=3$ 。那我们用上面的 $Code$ 是有可能得到 $x=7,y=0$ 这组解的。

那我们要怎么求最小正整数解呢？

首先，我们先将两组解列出来比较。

$\left\{ \begin{array}{lc} x_1=3 \\ y_1=3 \\ \end{array} \right.$

$\left\{ \begin{array}{lc} x_2=7 \\ y_2=0 \\ \end{array} \right.$

这个根据我们的数学直觉，我们可以发现，$x_1$ 和 $x_2$ 之间相差了 $4$ ，而这个 $4$ 正好是 $b$的值，同样，$y_1$ 和 $y_2$ 之间相差了 $3$,而这个 $3$ 正好是 $a$ 的值。那这样的话，$x$ 每次加上 $b$ 的值，$y$ 每次加上 $a$ 的值，结果会保持不变，我们就来试一下 $x=11,y=-3$ 这组解。而 $3*11+4*(-3)=21$ ,欸，刚好成立。

但是这个毕竟是我们的数学直觉，带有一定的玄学成分，不能说明是正确的，需要通过严谨的证明，所以下面我们来证明一下。

证明：

假设我们有两组解：

$ \left\{ \begin{array}{lc} ax_1+by_1=k\\ ax_2+by_2=k\\ \end{array} \right.$

那么我们联立方程可以得到：$ax_1+by_1=ax_2+by_2$ ，化简得：$a*(x_1-x_2)=b*(y_2-y_1)$

方程两边同时除以 $\gcd(a,b)$ ，得：$\dfrac{a}{\gcd(a,b)}*(x_1-x_2)=\dfrac{b}{\gcd(a,b)}*(y_2-y_1)$

由于 $\dfrac{a}{\gcd(a,b)}$ 和 $\dfrac{b}{\gcd(a,b)}$ 是互质的，所以可以得到：

$\dfrac{b}{\gcd(a,b)}$ 一定是 $(x1-x2)$ 的倍数，$(y1-y2)$ 一定是 $-\dfrac{a}{\gcd(a,b)}$ 的倍数，也就是通过两个解之间的差，我们就可以解出来通解。

通解公式：$ \left\{ \begin{array}{lc} x=x_0+\dfrac{b}{\gcd(a,b)}*t \\ y=y_0-\dfrac{a}{\gcd(a,b)}*t \\ \end{array} \right.$其中，$x_0,y_0$均为最小正整数解

化简得：$ \left\{ \begin{array}{lc} x_0=x-\dfrac{b}{\gcd(a,b)}*t \\ y_0=y+\dfrac{a}{\gcd(a,b)}*t \\ \end{array} \right.$

别忘了，这是线性同余方程，还得进行模运算才行。那么令 $dx=\dfrac{b}{\gcd(a,b)}$ ,$dy=\dfrac{a}{\gcd(a,b)}$,则有：
1. 若 $x$ 为正整数，则 $x_0=x\mod dx$
2. 若 $x$ 为负整数，那么要让 $x$ 变为正整数，只需要给 $x$ 加上 $dx$ 就可以了，则 $x_0=(x\mod dx+dx)\mod dx$
3. 综上所述，有：$x_0=(x\mod dx+dx)\mod dx$
注意，上面的通解公式只能用一条，另外一个解只能用 $(k-a*x)/b$ 或者 $(k-b*y)/a$ 来解，因为你两个解 $x$ 和 $y$ 的变化量是不一定相同的。

Code:

 void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
 {
     if(a==0){d=b;x=0;y=1;}
     else
     {
         LL tx,ty;exgcd(b%a,a,d,tx,ty);
         x=ty-(b/a)*tx;y=tx;
     }
 }
 int main()
 {
     LL a,b,k,d,x,y,m;
     scanf("%lld%lld%lld",&a,&b,&m);
     k=b;b=m;
     exgcd(a,b,d,x,y);
     if(k%d!=0)return 0;
     x=(k/d)*x;
     int dx=b/d,dy=a/d;
     x=(x%dx+dx)%dx;
     printf("%lld",x);
     return 0;
 }