题解 P1516 【青蛙的约会】

· · 题解

这是一篇有详细证明的题解 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);//处理负数 
}