【题解】洛谷P1516 青蛙的约会

题目

洛谷P1516青蛙的约会

题解

假设跳了t次以后相遇。列式变形后,解同余方程。

注意:欧几里得算法通常情况下默认参数a,b为正数,同时gcd(a,b)也为正数,所以要将参数转成正数,此处提供两种常用方法。

方法一:同余方程是在模意义下的,取参数在模意义下的最小正数即可。

方法二:对方程ax+by=c的所有参数a,b,c取相反数,等式仍成立,而且解不变。由于y不参与运算,所以b可以不变,对答案无影响。

更本质的研究:其实,用欧几里得算法递归求gcd时,即使a,b为负数也是有一定意义的,|gcd(a,b)|=gcd(|a|,|b|),下面有一段不严谨的验证代码。

所以,当a,b为负数时,也完全可以求出解。但是在求最小正数解时有一些不同,由于gcd<0,则通解的模数也小于0,直接取模可能是最小正数解,也可能是最大负数解,需要特判。

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月31日 下午2:48

*由于本人计算机水平较为蹩脚,本章解析可能并不准确。有存疑之处以#标注,望各位大神进一步解析。
【小白解析】
方法一:基本遵照同余方程的解题思路。其中gcd表示[两蛙每一次跳动的相对距离变化]与[纬线周长]的最大公因数,本质上代表了两蛙间距离(下文通称“间距”)在纬线上的最小变化“刻度”。#换句话说,间距%纬线长度一定是gcd的某个倍数;如果c正好为gcd的倍数则有解,反之无。第17行的判断即为此道理。
18行遵照先前同余方程的题解思路。c/gcd*x是在gcd=exgcd(((s1s2)%len+len)%len,len)的情况下,方程(((s1s2)%len+len)%len)*x+len*y=c的一特殊解#,18行操作保证结果取正。

方法二:思路基本与方法一相同。有读者可能好奇abs(s1-s2)>len的情况会不会有影响;这种情况下,gcd的有效取值范围其实依旧是1<=gcd<len;若gcd==len,间距实则没有变化。#

最终优化:实则是依照欧几里得算法的全能性制定的方法,基本思路依旧。
*验证为毛不用random()啊(恼)