首页 > 代码库 > 51nod 1831 小C的游戏(博弈论+打表)
51nod 1831 小C的游戏(博弈论+打表)
比较坑的题目。
题意就是:给出一堆石子,一次操作可以变成它的约数个,也可以拿只拿一个,不能变成一个,最后拿的人输。
经过打表发现
几乎所有质数都是先手必败的,几乎所有合数都是先手必胜的
只有几个例外,就是17^n, 2^n这些。
不过继续推导可以发现16是先手必败的,因为2,4,8,15都是先手必胜的
所以2^n(n>4)都是先手必胜的
17是先手必胜的,所以17^2是先手必败的,17^n(n>2)是先手必胜的
17*2是先手必败的
同理可以推导出2^n*17^m这些(当n>1或m>1)时是先手必胜的
#include <iostream> #include <cstdio> #include <map> #include <cstring> using namespace std; map<int, int> dp, visit; int main() { int T, x; cin>>T; while(T--){ scanf("%d", &x); int isp = 1; for(int i = 2; i*i <= x; i++) if(x % i == 0) isp = 0; if(isp) cout<<((x == 2) || (x == 17) ? "TAK" : "NIE")<<endl; else cout<<((x == 16) || (x == 34) || (x == 289) ? "NIE" : "TAK")<<endl; } return 0; }
51nod 1831 小C的游戏(博弈论+打表)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。