poj1061-青蛙的約會（擴展歐幾裡德算法），poj1061-裡德

poj1061-青蛙的約會（擴展歐幾裡德算法），poj1061-裡德

一，題意：

　　　兩個青蛙在赤道上跳躍，走環路。起始位置分別為x，y。
　　　每次跳躍距離分別為m，n。赤道長度為L。兩青蛙跳躍方向與次數相同的情況下，
　　　問兩青蛙是否有方法跳躍到同一點。輸出最少跳躍次數。
二，思路：
　　本題用到擴展歐幾裡德算法求二元一次不定式方程(ax+by=c)。
　　1,化簡方程，然後求解 ax+by = gcd(a,b);
　　2,求解 ax+by = c;
　　3,求出最小非負整數解x1
三，步驟： 
　　1,設青蛙跳了s步。
　　　則有方程 (x + m*s) - (y + n*s) = l*k  -->  (n - m)*s + l*k = x - y
　　　令 a = n - m , b = l , x' = s , y' = k , c = x - y ; d = gcd(a,b);
　　　所以方程化為 a*x' + b*y' = c ;
　　2,先利用擴展歐幾裡德算法求解方程 a*x' + b*y' = gcd(a,b);
　　3,利用方程 a*x' + b*y' = gcd(a,b) 的解 x0 以及公式 x = x0*c/d 求出 a*x' + b*y' = c 的解 x1 ; 前提是：d|c  ( c 能被 d 整除 );
　　4,利用周期性變化求最小的非負整數解 公式: x1 = ( x1%(b/d) + (b/d) ) % (b/d);
　　　若方程的a*x' + b*y' = c的一組整數解為(x1,y1)，則它的任意整數解為 ( x1 + k* ( b/d ) , y1 - k*( a/d ) )  ( k 取任意整數 ) , T = b/d 就為 x1 增長的周期
　　　　i，若x1為負值，取最大的非正值：x1 = x1 % T ;若x1為正值，以下兩步無影響。
　　　　ii，取正， x1 = x1 + T ;

　　　　iii， 防止 i中的x1=0 即 ii中的x1 = T ,那麼 x1 = x1 % T ;

1 #include<iostream> 2 using namespace std ; 3 4 //擴展歐幾裡德算法 : 用來求解 a*x+b*y=gcd(a,b) 方程x,y可能的值 5 void exgcd(long long a,long long b,long long& d,long long& x,long long& y){ //int& a 表示傳入a的地址 6 if(!b){d=a;x=1;y=0;} // d用來存儲gcd(a,b)的值 7 else {exgcd(b,a%b,d,y,x);y-=x*(a/b);} 8 } 9 10 int main(){ 11 long long minx,x,y,m,n,l,d,x1,y1,T; 12 cin>>x>>y>>m>>n>>l; 13 exgcd(n-m,l,d,x1,y1); //(n-m)*s+l*k = gcd(n-m,l) ==> x1=s y1=k; 14 if((x-y)%d!=0) cout<<"Impossible\n"; //方程有解的條件是：x-y 能被 gcd(n-m,l) 整除 15 else{ 16 x1=x1*((x-y)/d); //思路2中方程 a*x1 + b*y1 = c 的解 x1 ; 17 T=l/d; //x的增長周期 T 18 x1=(x1%T+T)%T;//求出最小非負整數解 19 cout<<x1<<endl; 20 } 21 return 0; 22 } View Code

 如發現錯誤或者有不理解的地方，請聯系我。