《信息学奥赛课课通（C++）》配套资料

Game算法： 判断输入时的两个数，如果有倍数关系或大数DIV小数大于等于2，则S胜； 否则将状态转为（大数-小数，小数）再度进行判断。 复杂度：O（1） 【note：为什么大数DIV小数大于等于2时为胜态？】 博弈问题 本质是通过（1,0）必败态向上推导 即面临（1,0）的人为输家（对方取得0） eg： （1,3）能推导出败态（1,0）所以为胜态 （4,3）只能推导出（1,3） 所以为败态 （4,7）能推导出败态（4,3）所以为胜态 （11,7）只能推导出（14,7）所以为败态 对于（25,7） 能推导出 败态（11,7）和 胜态（4,7）两个状态 意思是如果己方拿到的数是（25,7） 可以通过给对方败态（11,7）造成对方失败 所以（25,7）是胜态 由此可知 对于数对（n,m）（假设n<m）（p>=2） 如果（n,m）为败态 则 (n+m*p,m)为胜态 如果 (n,m)为胜态 则（n+m，m）只能走到（n,m）为败态 (n+m*p，m）可以通过变成（n+m，m）使对方陷入败态 因此（n+m*p，m）(p>=2)为必胜态 因此 当输入数大数DIV小数>=2时 S胜；