0 0 题解不是很懂啊 asked 2017-01-01 rejudgeX 0 rejudgeX 2017-01-01 我的意思是题解说的 辗转想减可逆这句给我感觉是难道这个解构造的逆过程一定是严格的辗转相减吗？感觉不一定吧， 这么随机化一下判断，有可能没法得到正解？ 添加评论 ✖reply submit comment
5 answer(s) 0 0.618就是黄金分割啊..最优情况下就是来回加这样步数最少，你算一下两个的比例就是0.618，所以就直接在这个附近找就可以了 2017-01-01 jiry_2 0 碳碳双键 2017-01-02 居然有这样神奇的事情，无脑随机者表示%%%（顺便%%%jiry_2 添加评论 ✖reply submit comment 0 在m=n/2附近找，你模拟一下发现肯定会有一个数两三步被减到很小，然后步数会爆。 实测0.618和完全随机差不多= = 2017-01-01 apiadu 0 添加评论 ✖reply submit comment 0 一定是啊，比如(a,b)->(a+b,b)，a+b肯定是>=b的，所以对于(a+b,b)就是大的减去小的 我直接瞎随机m就过了= = 2017-01-01 fjzzq2002 0 添加评论 ✖reply submit comment 0 其实就是枚举最后一步的m，这个m确定了，整个过程就确定了。 题解中的m是1-n随机的，所以我觉得合法的m应该挺多的，不会一直随不到超时。 至于在m = n*0.618附近找我不知道能不能证明比完全随机靠谱，不过看上去好像挺科学的。 2017-01-01 gtdzx 0 Zayin 2017-01-01 我就是在m = n*0.5附近随机找然后超时了。。。 添加评论 ✖reply submit comment 0 第一题的m是怎么求出来的？ 我看了ac的代码好些都是 m = n*0.618, 然后在 m 的附近找到最终与n互质的数，有啥数学定理或者证明吗？ 2017-01-01 sunshinestyle 0 添加评论 ✖reply submit comment
我的意思是题解说的 辗转想减可逆这句给我感觉是难道这个解构造的逆过程一定是严格的辗转相减吗？感觉不一定吧， 这么随机化一下判断，有可能没法得到正解？