POJ 1061 青蛙的約會 （擴充歐幾裡得）

擴充歐幾裡得算法在了解，第一次學的時候不是很深刻，沒做到真正的知行合一（最近比較崇拜王陽明）

擴充歐幾裡得就是求ax+by=gcd(a,b)的解，而且這個解一定會存在。

b=0,x=1;

a>b>0 時

設 ax1+ by1= gcd(a,b);

bx2+ (a mod b)y2= gcd(b,a mod b);

根據樸素的歐幾裡德原理有 gcd(a,b) = gcd(b,a mod b);

則:ax1+ by1= bx2+ (a mod b)y2;

即:ax1+ by1= bx2+ (a - [a / b] * b)y2=ay2+ bx2- [a / b] * by2;

也就是ax1+ by1 == ay2+ b(x2- [a / b] *y2);

根據恒等定理得：x1=y2; y1=x2- [a / b] *y2;

如果遇到a*x+b*y=c就朝這方面轉化

然後求ax + by = c，判斷c如果不能被d整除就Impossible，否則就令x = c/d * x0就可以得到一個x解了。

但有無數個解滿足ax + by = c的。為神馬呢？ax + by = c其實就等價于ax ≡ c (mod b)對不？如果我得到一個特解x*，

那麼加上若幹倍b還是這個方程的解，因為a(x*+k*b) = ax* + a*k*b ≡ c + 0 ≡ c (mod b)。因而方程在[0, b-1]上一定有整數解

（假如小于0，你加上若幹倍b啊，就可以讓它保持在0~b-1中；如果大于b-1，你減去若幹倍b啊，它也保持0~b-1）。

最後還要用到擴充歐幾裡得2個定理，第一次學的時候都沒看。。。

1、若gcd(a, b) = 1，則方程ax ≡ c (mod b)在[0, b-1]上有唯一解。

2、若gcd(a, b) = d，則方程ax ≡ c (mod b)在[0, b/d - 1]上有唯一解。

最後一步非負解 用x = (X % r + r) % r就可以求出最小非負整數解x了！（X % r可能是負值，此時保持在[-(r-1), 0]内，

正值則保持在[0, r-1]内。加上r就保持在[1, 2r - 1]内，是以再模一下r就在[0, r-1]内了）。

#include <iostream>
using namespace std;
long long ex_gcd(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=ex_gcd(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,d,r,x1,y1;
    while(cin>>x>>y>>m>>n>>L)
    {
       d=ex_gcd(n-m,L,x1,y1);
      r=L/d;
      if((x-y)%d)cout<<"Impossible"<<endl;
      else cout<<((x - y) / d*x1%r+r)%r<<endl;//然後求ax + by = c，判斷c如果不能被d整除就Impossible，否則就令x = c/d * x0就可以得到一個x解了。
    }
    return 0;
}
           

我也試過其他方法，會逾時，和擴充歐幾裡得一個思路，

國小生水準，是以逾時了

int main()
{
    long long x, y, m, n, L;
    while (cin >> x >> y >> m >> n >> L)
    {
        long long a=0,b=0;//a是目前的快的需要超越的圈數，b是快的比慢的快的速度
       if(m==n)cout<<"Impossible"<<endl;
       else if(m>n&&x>y)a=L-(x-y),b=m-n;
        else if(m>n&&x<y)a=x-y,b=m-n;
        else if(m<n&&x>y)a=y-x,b=n-m;
        else if(m<n&&x<y)a=L-(y-x),b=n-m;
       long long t=0;
       while(a%b!=0)
       {
           a=a+L;
           t+=a/b;
           a%=b;
       }
       t+=a/b;
       cout<<t<<endl;
    }
    return 0;
}