傳送門

根據(jù)題意可以列出方程：

設(shè)走了X步，已經(jīng)繞了維度線Y圈

那么? ?nX-mX=LY+(x-y)

稍微轉(zhuǎn)換一下： (n-m)X - LY = x-y

如果設(shè)? A=n-m,B=-L,C=x-y

那就變成了AX+BY=C的形式

直接套exgcd就可以得到一組AX+BY=gcd(A,B)的解

根據(jù)基本的數(shù)學(xué)知識，原方程有解當且僅當? gcd(A,B) | C? 時

然后把X和Y乘一個C/gcd(A,B)就是原方程的一組解（X,Y）了

然后要注意n-m為負的情況，要把方程兩邊同時乘-1（A=-A，C=-C）

Y的符號不重要，所以B乘不乘-1都沒關(guān)系

然后考慮得到一組解后如何求出最小解

可以發(fā)現(xiàn)兩只青蛙每走L/gcd(L,A)步后就都會回到出發(fā)點

所以只要把答案對L/gcd(L,A)取模就是最小解了

還要注意答案是負數(shù)的情況，這時答案為 (X%mo+mo)%mo

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef long long ll; ll exgcd(ll a,ll b,ll &x,ll &y) {if(!b) { x=1,y=0; return a; }ll g=exgcd(b,a%b,x,y);ll t=x; x=y;y=t-a/b*y;return g; } ll n,m,x,y,L; ll d,X,Y; int main() {cin>>x>>y>>m>>n>>L;ll A=n-m,B=x-y;//這里的B就是上面說的Cif(A<0) A=-A,B=-B;d=exgcd(A,L,X,Y);if(B%d) { printf("Impossible"); return 0; }ll ans=X*B/d,mo=L/d;printf("%lld",(ans%mo+mo)%mo);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/LLTYYC/p/9778812.html

總結(jié)

以上是生活随笔為你收集整理的P1516 青蛙的约会的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。