一只青蛙1一開始在x位置，另一只青蛙2在y位置。青蛙1每次跳m米，青蛙2每次跳n米，并且都是向右跳的。地球經線長度是L，然后地球是圓的，也就是說，對L取模；問多少次后它們能跳到一起。如果它們永遠不能相遇，就輸出Impossible

求一個k，使x + k*m ≡ y + k*n (mod L) ，就變成(n-m) * k ≡ x-y (mod L)咯。然后這個方程其實就等價于(n-m)*k + L*H = x-y咯。這就是ax + by = c求整數x的模型。

要求ax + by = c的整數x解；就可以利用擴展歐幾里得出答案；

View Code #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<set> #include<map> #include<cstring> #include<vector> #define LL long long using namespace std; LL ExGcd( LL a ,LL b ,LL &x ,LL &y) {if( b == 0 ){x = 1;y = 0;return a;}LL Mod = ExGcd( b , a % b , x ,y );LL temp = x;x = y;y = temp - (a/b) * y;return Mod; } int main( ) {LL x,y,n,m,L,X,Y;while( scanf( "%I64d %I64d %I64d %I64d %I64d",&x,&y,&n,&m,&L )==5 ){LL A = x - y,B = m - n;LL mod = ExGcd( B , L , X ,Y );if( A % mod ){printf( "Impossible\n" ); } else{B /= mod; L /= mod; A /= mod;LL temp = (A*X)%L;while( temp < 0 ) temp += L;printf( "%I64d\n",temp ); }}//system( "pause" );return 0; }

轉載于:https://www.cnblogs.com/bo-tao/archive/2012/07/18/2597570.html

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。