题目链接：https://vjudge.net/problem/POJ-1061
题意：在一个首位相接的坐标轴上，A、B开始时分别位于X,Y处，每个单位时间向右移动m,n米，问是否能相遇，坐标轴长L。
思路：与poj2115几乎一样，扩展欧基里德模板题。题意即X+m*x=Y+n*x (mod L)，x为最短相遇时间，转换后：(m-n)*x+L*y=Y-X (mod L)，令a=m-n,b=L,c=Y-X，可通过扩展欧基里德定理计算出a*x+b*y=gcd(a,b)，令d=gcd(a,b)。则原题有解等价与d整除c，且解为 ((c/d*x)%tmp+tmp)%tmp，tmp=abs(b/d)，因为a可能小于0，所以计算出来的c也可能小于0，所以tmp要取绝对值。
AC代码：
#include<cstdio> using namespace std; typedef long long LL; LL X,Y,m,n,L; void ex_gcd(LL a,LL b,LL &x,LL &y,LL &d){ if(!b) x=1,y=0,d=a; else{ex_gcd(b,a%b,y,x,d);y-=x*(a/b);} } int main(){ scanf("%lld%lld%lld%lld%lld",&X,&Y,&m,&n,&L); LL a=m-n,b=L,c=Y-X,x,y,d; ex_gcd(a,b,x,y,d); LL tmp=b/d; if(tmp<0) tmp=-tmp; if(c%d==0) printf("%lld\n",((c/d*x)%tmp+tmp)%tmp); else printf("Impossible\n"); return 0; }
原文：https://www.cnblogs.com/FrankChen831X/p/10813604.html