不被卡精度的方法
查看原帖
不被卡精度的方法
250222
zhenzitou楼主2024/12/26 14:04

题目可转化为判断 ⌊(y−x)5+12⌋=x (x≤y)\lfloor(y−x)\frac{\sqrt5+1}2\rfloor=x\ (x\leq y) 是否成立。(见题解)

然而题解都用的是浮点数,我这么做被卡精度了。此处提供一种可以不被卡精度的方法。

⇔x≤(y−x)5+12<x+1\Leftrightarrow x\leq(y−x)\frac{\sqrt5+1}2<x+1

令 y−x=z≥0y-x=z\geq0

⇔x≤z5+12<x+1\Leftrightarrow x\leq z\frac{\sqrt5+1}2<x+1 ⇔2x≤5z+z<2x+2\Leftrightarrow 2x\leq \sqrt5z+z<2x+2 ⇔2x−z≤5z<2x−z+2\Leftrightarrow 2x-z\leq \sqrt5z<2x-z+2

若 2x−z+2≤02x-z+2\leq0,显然不成立

否则若 2x−z<02x-z<0,

⇔5z2<(2x−z+2)2\Leftrightarrow 5z^2<(2x-z+2)^2

否则

⇔(2x−z)2≤5z2<(2x−z+2)2\Leftrightarrow (2x-z)^2\leq5z^2<(2x-z+2)^2

然后就转化为整数运算,不会被卡精度了。

2024/12/26 14:04
加载中...