蒟蒻数学不好所以看了很久才仿佛懂得了原理

参考原博
参考原博
参考百科

首先是

欧几里得算法

定理

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。
$$
gcd(a,b) = gcd(b,a mod b)
$$

证明

$a$可以表示成$a = kb + r（a，b，k，r$皆为正整数，且$r<b）$，则$r = a\ mod \ b$

假设d是a,b的一个公约数，记作$d|a,d|b$，即$a$和$b$都可以被$d$整除。

而$r = a - kb$，两边同时除以$d，r/d=a/d-kb/d=m$，由等式右边可知m为整数，因此$d|r$

因此$d$也是$b,a \ mod \ b$的公约数

假设$d$是$b$,$a\ mod \ b$的公约数, 则$d|b,d|(a-k*b),k$是一个整数。

进而$d|a$.因此$d$也是$a,b$的公约数

因此$(a,b)$和$(b,a\ mod\ b)$的公约数是一样的，其最大公约数也必然相等，得证。

扩展欧几里得定理

关于要求的问题

$gcd（a，b）=ax+by$的最小整数解

证明过程

首先$∵b≠0，有gcd（a，b）=gcd（b，a \mod\ b）;$
则令$∴bx’+（a \mod\ b）y’=gcd（b，a \mod \ b）;$
$∴ax+by=bx’+（a \mod \ b）y’；$

又$∵a \mod\ b=a-[a/b]*b$;($[x]$表示表示小于等于$x$的最大整数）

$∴ax+by=bx’+(a-[a/b]b)y’;$

整理得到$ax+by=ay’+b(x’-[a/b]*y’)$

于是就有了特殊解$x=y’,y=x’-[a/b]*y’;$

注意到当b=0是有一组$x=1,y=0$的特殊解

这是所谓的临界情况，根据以上的式子可以用递归层层找答案，就是不断地$exgcd(b,a \mod \ b)$直到求到b=0，

再层层找答案，不断地根据以上的式子返回答案，直到求到第一层的答案。

总之递归过程很玄学大概是这样

用扩欧解同余方程

题目描述（模板）

求关于 x 的同余方程 $ax ≡ 1 (mod b)$的最小正整数解。

解法

以上式子化简为$ax%b=1;$
$∴ax=by+1;$
$∴ax-by=1;$
$∴ax+by=gcd(a,b);$
注意此题中必须满足a，b互质，所以就是裸的扩欧
注意可能有负数解，所以要$（x+b）mod \ b；$

代码

#include <bits/stdc++.h>
#define N 100000+110
using namespace std;
int a,b,ans,sum,y,x;
void exgcd(int a,int b,int &x,int &y)
{
    if(!b){x=1;y=0;}
    else
    {
         exgcd(b,a%b,y,x);
        y-=(a/b)*x;
    }

}
int main()
{
    scanf("%d%d",&a,&b);
    exgcd(a,b,x,y);
    printf("%d",(x+b)%b);

    return 0;
}

另外此题也可用扩欧轻松解决

虽然我也不知道为啥这就是最小正整数解

线性同余

关于 x 的模方程$ ax%b=c$ 的解

方程转换为$ ax+by=c$ 其中 y 一般为非正整数

则问题变为用 exgcd 解不定方程

解得$ x_1=x_0 \times c/t$

通解为 $x=x_1+b/r \times t$

设 $s=b/r $（已证明 $b/r$ 为通解的最小间隔）

则 x 的最小正整数解为

$ (x_1 \%s+s)\%s$
证明：

若 $x_1>0$，

则 $(x_1 \%s+s)\%s=x_1\%s+s\%s=x_1\%s=x_1-ts (t∈N)$

若 $x_1<0，$因在 C++ 里

$a\ mod\ b=-(-a\mod\ b)<0 $, $(a < 0,b>0)$

如$ -10\%4=-2​$

则

$ (x_1\%s+s)\%s=(-(-x_1\%s)+s)\%s=(-(ts-x_1)+s)\%s=ts-x_1 (t∈N) $

即为 $x_1$ 通过加或减上若干个 s 后得到的最小正整数解

拓展——用扩欧解不定方程

解法大概是转化为 $gcd（a，b）=ax+by$的形式

对于 $ax+by=c$ 的不定方程，设 $r=gcd(a,b)$

当 $c%r!=0$ 时无整数解

当$ c%r=0$ 时，将方程右边 $*r/c $后转换为 $ax+by=r$ 的形式

可以根据扩展欧几里得算法求得一组整数解 $x0 , y0$

而这只是转换后的方程的解，原方程的一组解应再 $*c/r$ 转变回去

（如 $2x+4y=4 $转换为 $2x+4y=2 $后应再将解得的 x , y 乘上2）

则原方程解为

$x_1=x_0 \times c/r $,$y_1=x_0 \times c/r$

通解

$ x=x_1+b/r \times t $,$ y=y_1-a/r \times t $，

其中 t 为整数

证明：

将 x , y 带入方程得

$ax+ab/r \times t+by-ab/r \times t=c$

$ ax+by=c$
此等式恒成立

这里 $b/r$ 与 $a/r $为最小的系数，所以求得的解是最多最全面的

为了推出证明中的 $ax+by=c$ ，且想达到更小的系数，只能将 $b/r$ 与 $a/r$ 同除以一个数 s

而 $b/r$ 与 $a/r$ 互质，且 s 为整数，则 s=1 ，不影响通解

那么 $b/r $与 $a/r$ 就为最小的系数

模板（WA ‘s Date）

由题意得$（x+mk)\%l=(y+nk)\%l;$

令$A=y-x,B=m-n,k=x;$

移向整理得$(A+Bk)\%l=0$;

$∴A+Bk=ly;$

$∴Bx-ly=A;$

于是就转化到不定方程

注意gcd可能为负数，要abs

注意long long

代码如下

#include <bits/stdc++.h>
#define N 100000+110
#define ll long long
using namespace std;
ll a,b,ans,sum,y,x,A,B,l,gcdd,X0,Y0,m,n;
void exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b){x=1;y=0;}
    else
    {
         exgcd(b,a%b,y,x);
        y-=(a/b)*x;
    }

}

int gcd2(ll a,ll b)
{
    return !b?a:gcd2(b,a%b);
}
int main()
{
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
    A=y-x;B=m-n;
    gcdd=gcd2(l,B);
    if(A%gcdd!=0)printf("Impossible");
    else
    {
        int k=A/gcdd;
        exgcd(B,l,X0,Y0);
        printf("%lld",((X0*k+abs(l/gcdd))%abs(l/gcdd)));
    }

    return 0;
}

​