[BZOJ 1477]青蛙的约会
设用时为[tex]t[/tex]，则本题可视为解方程[tex](mt+x)-(nt+y)=kL[/tex]。
整理变形得[tex](n-m)t+Lk=x-y[/tex]。
明显需要扩欧求解。注意此题有很多细节，可参见下代码：
/**************************************************************
Problem: 1477
User: danihao123
Language: C++
Result: Accepted
Time:0 ms
Memory:1288 kb
****************************************************************/
#include <iostream>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
if(!b)
return a;
else
return gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
if(!b){
d=a;
x=1;
y=0;
}else{
exgcd(b,a%b,d,x,y);
ll t=x;
x=y;
y=t-a/b*y;
}
}
int main(){
ll a,b,c,t,M,k;
ll x,y,m,n,L;
cin>>x>>y>>m>>n>>L;
a=n-m;
b=L;
c=x-y;
k=gcd(a,b);
if(c%k!=0){
cout<<"Impossible"<<endl;
return 0;
}
a/=k;
b/=k;
c/=k;
exgcd(a,b,k,t,M);
t=(((c*t)%b)+b)%b;
if(!t)
t+=b;
cout<<t<<endl;
return 0;
}
