hihocoder1473 : 小Ho的强迫症
Intuition
步长为 F,台阶长 L,每次走 D。
因为无限走下去,位置是有限集,所以必然有循环节。
设起始位置脚后跟到上一个缝隙的长度为 X
,可以得到 (X + a * D) % L
为之后的位置,a
为步数,第一次回到起始位置时,a
为 L / gcd(D, L)
。
所以位置集合为 {X, X+gcd, X+2gcd, ..., X+L-gcd}
,要求最有可能踩到缝隙的结果为 X+L-gcd
,要保证 X+L-gcd + F < L
,就能保证成立。
所以 X
最好为 0,即 gcd < F
成立。
Solution
Last updated