Beaver Game CodeForces - 78C 【博弈论】

CodeForces 78C

题意

有两只beaver，n个木块，每个都是m长。每一次，一个beaver可以选一块木头咬成多于1个的等长木块，而且每块木块长度是整数且不大于k。如果这个beaver不能玩了，那么另一只beaver赢。
Timur是先手，Marsel是后手。输出赢家。
\(n,m,k (1\leq n,m,k\leq 10^9 )\)

思路

• 博弈我真是做一题错一题
• 参考网络资料
• n是偶数的话，后手赢，后手一直模仿先手就好了。
• n是奇数的话，如果\(m\)有不小于 \(k\) 的非平凡因子，那么就可以把这个木块分成若干根不能再分的小木块，于是后手面对着偶数个木块（n-1块），所以这时先手赢。
• 注意 i从1开始到\(i*i\leq m\)结束，枚举可能切成的木块大小
• 如果\(1<i<k,\frac{m}{i}\geq k\), 那么m/i是m的一个不小于k的非平凡因子，所以是先手赢。注意i不能为1.
• 如果\(i\geq k, \frac{m}{i}>1\)，那么i是m的一个不小于k的非平凡因子，所以是先手赢。注意m/i不能为1.这两个不给为1的情况都是为了防止不分木块的情况。
• 如果i从2开始的话，考虑\(n==1,m==2,k==1\)的情况，虽然i==1,但是这里是把长为2的木块分成两块长为1的木块，所以是可以的。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int main(){
	scanf("%d%d%d",&n,&m,&k);
	bool flag=false;
	if(n&1){
		for(int i=1;i*i<=m;i++){
			if(!(m%i)){
				if(((m/i)>=k&&i>1)||(i>=k&&(m/i)>1))
				{	flag=1;break;}				
			}
		}
	}
	printf(flag?"Timur\n":"Marsel\n");
	return 0;
} 

Beaver Game CodeForces - 78C 【博弈论】

原文：https://www.cnblogs.com/xuwanwei/p/12804036.html