题目地址：POJ 1061
扩展GCD好难懂。。看了半天，终于把证明什么的都看明白了。。推荐一篇博客吧（戳这里），讲的真心不错。。
直接上代码：
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 LL X, Y; LL exgcd(LL a, LL b) { if(b==0) { X=1; Y=0; return a; } LL r=exgcd(b,a%b); LL t=X; X=Y; Y=t-a/b*Y; return r; } int main() { LL x, y, m, n, l, L, d; while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l)!=EOF) { if(m>n) { d=exgcd(m-n,l); L=y-x; } else { d=exgcd(n-m,l); L=x-y; } //printf("%I64d %I64d\n", X, Y); if(m==n||L%d) { printf("Impossible\n"); continue ; } LL ans=X*L/d; LL s=l/d; //printf("%I64d %I64d %I64d\n",X, ans,s); if(ans<=0) ans=ans%s+s; else ans=ans%s; printf("%I64d\n",ans); } return 0; }