作者babufong (哔哔)
看板puzzle
标题[中译] ProjectEuler 325 Stone Game II
时间Sun Feb 20 20:01:05 2011
325. Stone Game II
http://projecteuler.net/index.php?section=problems&id=325
这游戏的玩法是两个人与两堆石头。
在她的回合，她从较大堆的石头中移除掉一些石头。
移除掉的石头数量必须为较小堆石头的正整数倍。
举个例子，(6,14)表示为较小堆的石堆有6颗石头，较大堆的石堆有14颗石头
先手可以从较大堆的石堆中拿6或12颗石头。
从某一堆拿走全部石头的玩家就胜利。
必胜型指的是先手可以迫使局面成为先手胜利。例如：(1,5) , (2,6) 还有 (3,12)
都是必胜型，因为先手可以马上移除掉较大堆的石堆中所有的石头。
必败型指的是後手可以迫使局面成为後手胜利，无论先手做了什麽动作。
例如：(2,3) 和 (3,4) 都是必败型，先手任何合法动作皆会留下一个必胜型给後手。
定义 S(N) 为所有必败型 (xi,yi) 且 0 < xi < yi <= N 中，(xi+yi) 的总和
我们可以知道 S(10) = 211 且 S(10^4) = 230312207313。
请算出 S(10^16) mod 7^10。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 125.224.1.79
1F：推 LPH66:....我在家里的一本数学书上看到这个玩法但已经忘了结论了QQ 02/20 20:07
2F：推 jurian0101:Nim - 天文数字篇 (开学了，ProEuler掰掰~~~~) 02/20 20:54
5F：→ utomaya:不过这公式复杂度是O(N) 要算到S(10^16) 还要一点辅助 02/20 21:40
6F：→ utomaya:我确定没有别的公式了 这就是ProjectEuler贼的地方 02/20 21:41
7F：→ utomaya:光靠公式 还不足以解出；；不然的话 20席早满了 02/20 21:42
8F：→ utomaya:ProjectEuler那些玩家 搜寻公式可是很厉害的! 02/20 21:43
9F：→ utomaya:有时候 解个半死 ；进到论坛，才发现别人早就找到公式了 02/20 21:44
10F：→ utomaya:这公式是没错的, 我验证过, S(10^4)一下就出来了 02/20 21:46
11F：→ utomaya:如果你不想看那麽多 直接跳到定理7, 那里有结论 02/20 21:47
12F：→ utomaya:还有，解题的关键 不在这个公式(非常确定)，要靠自己! 02/20 21:49
13F：推 utomaya:解题的关键 应该在费氏数列的特性 Fn=Fn-1+Fn-2 02/20 21:52
14F：→ utomaya:要用divide and conquer去做 很难写! 所以第1天只有13人 02/20 21:53
15F：→ utomaya:应该这样说吧 利用这公式在计算时 你会发现很多计算是重复 02/20 21:54
16F：→ utomaya:所以可以把计算的部份重复的部份 用divide and conquer 02/20 21:56
17F：→ utomaya:去化简! 02/20 21:56
发现我有打错的地方 已修改！
※ 编辑: babufong 来自: 125.224.9.7 (02/20 22:15)
18F：推 utomaya:对了 为了怕误导大家 我再把话说清楚一点 02/21 00:30
19F：→ utomaya:解题的关键 不在这个公式, 不是说不要利用这个公式 02/21 00:30
20F：→ utomaya:当然还要利用公式，只是不要尝试再去化简公式 02/21 00:31
21F：→ utomaya:这公式已经是最简了 02/21 00:31
22F：推 utomaya:果然跟猜想的一样 利用fibonacci数列的特性 02/23 06:57
23F：→ utomaya:S(10^16)mod 7^10 不用一毫秒 答案就出来了 复杂度O(logN) 02/23 06:59