题意:中文题 不解释了
思路:两只青蛙跳了t步,A的坐标是x+mt,B的坐标是y+nt。它们相遇的时间的充要条件是:x+mt-y-nt=pL
即:(n-m)t+Lp = x-y ----- ax+mx= b解这个同余方程的非负整数解就行
x0解出的是ax+mx=d(d是a , b最大公约数) 有解的时候 d|b 所以把x0扩大d/b倍数即可
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; void exgcd(ll a , ll b , ll &d , ll &x , ll &y) { if(b == 0) { d = a; x = 1; y = 0; return; } exgcd(b , a%b , d , x , y); ll tmp = x; x = y; y = tmp - (a/b)*y; } int main() { ll x , y , m , n , L; while(cin>>x>>y>>m>>n>>L) { ll d , x0 , y0 , ans; exgcd(n - m , L , d , x0 , y0); ans = x0*(x-y)/d; if((x-y)%d) { printf("Impossible\n"); } else { if(ans>0) cout<<ans%(L/d)<<endl; else cout<<(ans%(L/d)+L/d)%(L/d)<<endl; } } }