同余方程

前置知识：

• 裴蜀定理

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

裴蜀定理：

• 定义：裴蜀定理，又称贝祖定理，是一个关于 \(gcd\) 的定理。

• 内容：设 \(a,b\) 整数，则存在整数，使得 \(ax+by=\gcd(a,b)\)

• 证明：略。

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

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

• 推导：

1. 由裴蜀定理得：\(ax+by=\gcd(a,b)\),

2. 化简得：\(ax+by=\gcd(b,a\mod b)\),

3. 构造方程：\(bx_0+(a\mod b)y_0=\gcd(b,a\mod b)\),

4. 由模运算的定义，有：\(a\mod b=a-\left\lfloor\dfrac{a}{b}\right\rfloor*b\),

5. 因此，原方程化简为：\(bx_0+(a-\left\lfloor\dfrac{a}{b}\right\rfloor*b)y_0=\gcd(b,a\mod b)\),

6. 联立方程，得：

\( \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. \)

7. 根据对应系数相等，得：
   \( \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\) 算法。

1. 由模运算的定义，有：$ax=k-y*b \pmod b $

2. 移项得：\(ax+by=k \pmod b\)

3. 最后，使用 \(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;
   }