自动搬运

查看原文

来自洛谷，原作者为

	皎月半洒花 在那之前，你要多想。

搬运于2025-08-24 21:25:58，当前版本为作者最后更新于2018-04-12 21:57:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这是一篇有详细证明的题解 $qwq$~

首先我们可以发现，这个题就是为了让我们解一个方程：

$$x+km\equiv y+kn\pmod{l}$$

其中 $k$ 为所求。

让我们把这个看上去很 zz 的方程变化一下：

$$x+km-(y+kn)=lz,z \in Z$$

那么就是：

$$\begin{aligned} x-y+k(m-n)-lz&=0\\ k(m-n)-lz&=-(x-y) \end{aligned} $$

我们设 $S=x-y,W=n-m$（注意这个地方有变号，即 $m-n$ 被我设作 $n-m$，为的是让等式右边的 $S$ 冠正号）。

这个式子便可写作：

$$kW+lz=S$$

诶，这不就是一个不定方程吗？

对啊，所以我们所要做的就是对这个不定方程求出最小解。

那么其实，对于这个方程，我们是要解出步数的最小值，所以我们只需要求出$k$最小即可。我们可以通过扩展欧几里德算法求出一组特解，然后对于这组特解，我们再推导出最小解来。

但由于这个方程在解 $exgcd$ 的时候，那个方程转化成了：

$$k_jW+lz_j=(W,l)$$

那么我们求出的 $k_j$ 就是这个方程得一个特解。

之后，这个方程的所有解就可以表示成

$$k_i=k_j+t\frac{l}{gcd(W,l)}$$

---

这是上面这个式子为什么可以这么做的证明：

若有 $ax+by=c$ 且 $a_0x+b_0y=c$。

那么便有 $a(x-x_0)+b(y-y_0)=0$。

两边同时除以 $gcd(a,b)$ 可得

$$\frac{a}{gcd(a,b)}(x-x_0)=-\frac{b}{gcd(a,b)}(y-y_0)\quad (1) $$

而因为

$$(\frac{a}{gcd(a,b)},\frac{b}{gcd(a,b)})=1$$

所以由 $(1)$ 可得 $\frac{b}{gcd(a,b)}$ 整除 $(x-x_0)$。

所以很显然有

$$\frac{b}{gcd(a,b)}\times{t}={(x-x_0)},t \in \mathbb{Z} $$

那么就有对于任意一个 $x_i$，有

$$x_i=x_0+\frac{b}{gcd(a,b)} \times{t}$$

---

---

让我们回到原问题。因为

$$k_j=k_{min}+\frac{l}{gcd(W,l)} \times{t}$$

这个方程对于 $t \in Z$ 而言，想要通过一个特解推出最小解，可以如此做：

$$k_{min}=k_j \bmod \frac{l}{gcd(W,l)}$$

而因为这个 $k$ 是建立在 $\rm exgcd$ 得出的方程上的，方程右边是 $gcd(W,l)$ 而不是 $S$。所以最后我们需要将结果 $\times{ \frac{S}{gcd(W,l)} }$ 。

ll ans,x1,y1;

ll exgcd(ll a,ll b,ll &x1, ll &y1){
    if(!b){
        x1=1;
        y1=0;
        return a;
    }
    ans=exgcd(b,a%b,x1,y1);
    ll t=x1;
    x1=y1;
    y1=t-a/b*y1;
    return ans;
}

int main(){
    ll n,m,x,y,l;
    cin>>x>>y>>m>>n>>l;
    ll b=n-m,a=x-y;
    if(b<0){
        b=-b;
        a=-a;
    }//处理负数 
    exgcd(b,l,x1,y1);
    if(a%ans!=0)//判断方程有无解。 
        cout<<"Impossible";
    else
        cout<<((x1*(a/ans))%(l/ans)+(l/ans))%(l/ans);//处理负数 
}