社区讨论

不被卡精度的方法

P2252【模板】威佐夫博弈 / [SHOI2002] 取石子游戏参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m54x61zr
此快照首次捕获于
2024/12/26 14:04
去年
此快照最后确认于
2025/11/04 12:20
4 个月前
查看原帖
题目可转化为判断 (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
然后就转化为整数运算,不会被卡精度了。

回复

2 条回复,欢迎继续交流。

正在加载回复...