| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 89206 | Accepted: 15926 |
Description
Input
Output
Sample Input
1 2 3 4 5
Sample Output
4
Source
两只青蛙向同一方向跑，且最后相遇，那么所有的长度之差一定是总长的整数倍，即有 （x+m*t ) - (y+ n*t)=kL ,x为第一只青蛙的起点，m为其速度，y为第二只青蛙的起点，n为其速度。
x+mt-y-nt=kL
x-y+(m-n)*t=kL
(m-n)*t - kL = y-x
(m-n)t=(y-x)(mod L)
我们要求的是t，用扩展欧几里得就可以了，如果 (y-x)%gcd(m-n,L) !=0,则无解。
代码：
#include <iostream>
using namespace std;
typedef long long ll;
ll s1,s2,m,n,L;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
ll d=exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
return d;
}
int main()
{
cin>>s1>>s2>>m>>n>>L;
ll a=m-n;
ll b=s2-s1;
ll x,y;
ll d=exgcd(a,L,x,y);
if(b%d!=0)
cout<<"Impossible"<<endl;
else
{
ll x0;
x0=(x*b/d)%L;
ll ans=x0,s=L/d;
ans=(ans%s+s)%s;
if(ans<0)
ans=(ans+L)%L;
cout<<ans<<endl;
}
return 0;
}
[ACM] POJ 1061青蛙的约会（扩展欧几里得求模线性方程）,布布扣,bubuko.com
[ACM] POJ 1061青蛙的约会（扩展欧几里得求模线性方程）
原文：http://blog.csdn.net/sr_19930829/article/details/38232191