poj1061 青蛙的约会 解二元一次不定方程

题目链接：http://poj.org/problem?id=1061

题目题目：在一个周长为L的圆圈上两只青蛙分别在s1,s2,速度（步长）分别为v1,v2,它们往同一风向走，问几步后相遇。

依然是扩展欧几里德，要注意的是这里数据范围很大，用64位并且用gcd处理一下，之前没处理就wa了好多次。

代码如下：

//============================================================================// Name        : poj1061.cpp// Author      : ssslpk// Version     :// Copyright   : Your copyright notice// Description : Hello World in C++, Ansi-style//============================================================================#include <iostream>#include<cmath>using namespace std;#define int64 long longint64 a,b,c,d,x,y;int64 gcd(int64 a,int64 b){return b? gcd(b,a%b):a;}int64 exgcd(int64 a,int64 b){if(b==0){x=1;y=0;return a;}d=exgcd(b,a%b);int64 xx=y,yy=x-a/b*y;x=xx;y=yy;return d;}int main() {int64 s1,s2,v1,v2,l;while(cin>>s1>>s2>>v1>>v2>>l){if(v1>v2){a=v1-v2;b=l;c=s2-s1;}else {a=v2-v1;b=l;c=s1-s2;}d=gcd(a,b);if(c % d){cout<<"Impossible"<<endl;continue;}a/=d;b/=d;c/=d;d=exgcd(a,b);x*=c;x=(x%b+b)%b;cout<<x<<endl;}return 0;}