青蛙的约会
| Time Limit: 1000MS |
|
Memory Limit: 10000K |
| Total Submissions: 82940 |
|
Accepted: 14442 |
Description
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
Input
输入只包括一行5个整数x，y，m，n，L，其中x≠y <2000000000，0
Output
输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"
Sample Input
1 2 3 4 5
Sample Output
4
Source
浙江
我做出这个题目的时候内心痛苦极了，我卡这个题已经很久了，看了各种博客才终于明白了，唉，就在我做出这个题
这个上午我感觉失去了我的青春。莫把幺弦拨。怨极弦能说。天不老，情难绝。心似双丝网，中有千千结。 夜过
也，东窗未白凝残月。唉，还是acm对待每个人最为公平，只要你愿意去干！！！！
这个题目的中青蛙a 的坐标是x+mt,青蛙b 的坐标是y+nt.他们相遇的条件是x+mt-(y+nt)=pL,换一下行就是（n-m)t+
Lp=x-y,令n-m=a,p=b,x-y=c,则这就是标准的扩展欧几里得嘛（唉，这个世界上总是有这么一批人，明明自己死了
也不让别人活，），就是ax+by=c,那么扩展欧几里得的定理是什么呢？？gcd(a,b)=xa+yb;如果gcd(a,b)=1,则a，b是
互素的，那标准的欧几里得是怎么推出来的呢？？
ax0 + by0 = gcd(a, b) = gcd(b, a%b) = bx1 + (a%b)y1，而a%b又可以写成a-a/b*b，所以=bx1 + (a-a/b*b)y1 =
ay1 + b(x1-a/b*y1)，所以如果我们求出gcd(b, a%b) = bx1 + (a%b)y1的x1和y1，那么通过观察就可以求出x0 =
y1，y0 = (x1 - a/b*y1)。这样逐层去求就可以最终得出了！！！！
例如当我们把a=3,b=9,时，这个式子会推出来3*1+9*0=3，这是C会是3,9的最大公约数，也就是gcd(3,9);
x=1,y=0 ；
如果给出的c不能够整除3，也就肯定是错了的！！！！！但这时我们要求出的x的最小非副值，那么这样我们又该如
何去求呢？？？
这就是如何去求通解了！！！！
唉，我看了别人的博客看了好久啊！！！！
如果得到ax ≡ c (mod b)的某一特解X，那么我令r = b/gcd(a, b)，可知x在[0, r-1]上有唯一解，所以我用x = (X % r + r) % r就可以求出最小非负整数解x了！（X % r可能是负值，此时保持在[-(r-1), 0]内，正值则保持在[0, r-1]内。加上r就保持在[1, 2r - 1]内，所以再模一下r就在[0, r-1]内了）。
#include
using namespace std;
long long exgcd(long long a, long long b, long long &x, long long &y)
{
long long d, t;
if (b == 0) { x = 1; y = 0; return a; }
d = exgcd(b, a % b, x, y);
t = x - a/b*y; x = y; y = t;
return d;
}
int main()
{
long long x,y,m,n,l,X,Y,t;
long long a,b,c;
while(cin>>x>>y>>m>>n>>l)
{
a=n-m;
b=l;
c=x-y;
long long r=exgcd(a,b,X,Y);
cout< if(c%r)
{
cout<<"Impossible"< }
else
{
long long s=l/r;
X=X*(c/r);
X=(X%s+s)%s;
cout<
}
}
return 0;
}
京公网安备 11010802041100号