poj 1061 青蛙的约会 (扩展欧几里得算法(负数的处理))

 

 

 

题目链接

题意:两只青蛙初始在数轴的x,y点,单位时间内分别可以向右跳m米和n米,数轴是环型的,长度为L,问两只青蛙能否相遇,以及相遇时跳的次数。

思路:相遇就是同一时间在同一地点。

 那么有方程 x+ C*m = y + C*n + k*L 其中C为跳的次数,k为之间差了L的个数(可以理解为被套圈的圈数)

化简得到 C(m-n) + K*L = y-x.

根据裴蜀定理,该方程有解,当且仅当y-x是gcd(m-n,L)的倍数。

然后根据扩展欧几里得算法,需要注意的是其中可能有负数。

如果a是负数,可以把问题转化成

\left|a\right|(-x)+by=\gcd(|a|,b)\left|a\right|为a的绝对值),然后令x'=(-x)

第二个需要注意的是,扩展欧几里得算法求出的是ax+by=gcd(a,b)的解,x,y还要乘对应的倍数才能得到正确的解。

第三个需要注意的是,跳的次数一定为正,这是隐含条件。

用了上道题用的while去得到第一个大于0的X会TLE

所以其实 X = ( X % gx + gx) %gx就好。。。? (其中gx = b/gcd(a,b))

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz