题解 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)} }$ 。 ```cpp 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);//处理负数 } ```