一,題意:
兩個青蛙在赤道上跳躍,走環路。起始位置分別為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 ;
如發現錯誤或者有不理解的地方,請聯系我。