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

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

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

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

yx=z0y-x=z\geq0

xz5+12<x+1\Leftrightarrow x\leq z\frac{\sqrt5+1}2<x+1 2x5z+z<2x+2\Leftrightarrow 2x\leq \sqrt5z+z<2x+2 2xz5z<2xz+2\Leftrightarrow 2x-z\leq \sqrt5z<2x-z+2

2xz+202x-z+2\leq0,显然不成立

否则若 2xz<02x-z<0

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

否则

(2xz)25z2<(2xz+2)2\Leftrightarrow (2x-z)^2\leq5z^2<(2x-z+2)^2

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

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