【扩展欧几里德】Vijos P1009 清帝之惑之康熙

题目链接：

　　https://vijos.org/p/1009

题目大意：

　　两个人，一个在坐标x，每天走m，一个在坐标y，每天走n，坐标长L，问几天后碰面。

题目思路：

　　【扩展欧几里德】

　　根据同余方程的ax+by=c，可以得出a=n-m,b=l,c=x-y 之后扩展欧几里得求线性同余方程。

　　题目数据较大需要使用long long

 //

 //by coolxxx

 //

 #include<iostream>

 #include<algorithm>

 #include<string>

 #include<iomanip>

 #include<memory.h>

 #include<time.h>

 #include<stdio.h>

 #include<stdlib.h>

 #include<string.h>

 #include<stdbool.h>

 #include<math.h>

 #define min(a,b) ((a)<(b)?(a):(b))

 #define max(a,b) ((a)>(b)?(a):(b))

 #define abs(a) ((a)>0?(a):(-(a)))

 #define lowbit(a) (a&(-a))

 #define sqr(a) (a)*(a)

 #define swap(a,b) (a)^=(b),(b)^=(a),(a)^=(b)

 #define eps 1e-8

 #define MAX 0x7f7f7f7f

 #define INF 20000

 #define PI 3.1415926535897

 #define N 100004

 using namespace std;

 int n,m,lll,ans,cas;

 long long x,y,a,b,c,d;

 long long exgcd(long long a,long long b)

 {

     if(!b)

     {

         x=;y=;

         return a;

     }

     d=exgcd(b,a%b);

     cas=x;

     x=y;

     y=cas-(a/b)*y;

     return d;

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

 //    freopen("1.txt","r",stdin);

 //    freopen("2.txt","w",stdout);

     #endif

     int i,j,k;

     while(~scanf("%d",&n) && n)

     {

         x=n;

         scanf("%lld%lld%lld%lld",&y,&m,&n,&b);//(n-m)X mod b = x-y; aX mod b = c

         a=((m-n)%b+b)%b;

         c=((y-x)%b+b)%b;

         d=exgcd(a,b);

         if(c%d!=)

         {

             puts("Impossible");

             continue;

         }

         a/=d;b/=d;c/=d;

         exgcd(a,b);

         x=(x%b+b)%b;

         x=(x*c)%b;

         printf("%lld\n",x);

     }

     return ;

 }

 /*

 //

 //

 */