求青蛙的约会,实质上就是算二元一次方程,这里要用到辗转相除法,即拓展的欧几里得算法:gcd(a,b)=gcd(b,a%b);
可以推导出:x=y';y=x'-(a'/b')*y';然后利用迭代法,可以求出a'x‘+b'y’=c'的解x',y';x=x'(x-y)/M;
(这里的算法思想就是这样的,如果不明白可看我的具体代码:)
#include<iostream>
using namespace std;
typedef long long int64;
int64 extend_gcd(int64 a,int64 b,int64 &x,int64 &y )
{
if(b==0)
{
x=1;y=0;return a;
}
int64 ret=extend_gcd(b,a%b,x,y);
int64 t=x-a/b*y;
x=y;
y=t;
return ret;
}
int main()
{
int64 x,y,m,n,L;
int64 ar,br;
int64 M;
cin>>x>>y>>m>>n>>L;
M=extend_gcd(n-m,L,ar,br);
if((x-y)%M||m==n)
cout<<"Impossible"<<endl;
else
{
int64 s=L/M;
ar=ar*((x-y)/M);
ar=(ar%s+s)%s;
cout<<ar<<endl;
}
return 0;
}