【POJ-2505 A multiplication game】
题意： 给定一个数n （1 < n < 4294967295）从1开始， 可以乘以 【2， 9】中的任意一个数字， 最先乘法运算后最先大于等于n的那个人胜利。
分析： 博弈问题一般先找规律。 我们发现， 当n的范围在【2， 9】之间时， Stan必胜， 因为Stan第一轮可以乘以【2， 9】中的任意一个数字。Stan的策略是使得他的每一步都能达到N状态。那么他的策略就是使得他的值尽可能快的到达n。 同理当n的范围在 【10， 18】 之间时， Ollie必胜， 因为Ollie也可以乘以【2， 9】中的任意一个数字使得他的必胜范围为【10， 2×9】。 Ollie的策略是使得他的每一步都达到P状态， 那么她的策略就是值尽可能最慢到达n。
根据以上分析， 我们可以得到：
【2， 9】 N状态， Stan必胜
【9+1， 29】P状态， Ollie必胜
【29 + 1， 299】N状态， Stan必胜
【299 + 1, 299*2】 P状态， Ollie必胜
所以我们可以根据上述的规律打表然后判断n状态出现的奇偶性。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;//[2, 9] stan
//[10, 2*9] ollie
//[2*9 + 1, 2*9*9] stan
//[2*9*9 + 1, 2*9*9*2] ollielong long sg[] = {2, 9, 18, 162, 324, 2916, 5832, 52488, 104976, 944784, 1889568, 17006112, 34012224, 306110016, 612220032, 5509980288 };int main () {long long n;while (cin >> n) {int cnt = 1;for (int i = 1; i < 17; i++) {if (sg[i] < n) {cnt++;} else {break;}}cout << (cnt % 2 ? "Stan" : "Ollie") << " wins." << endl;}return 0;
}