「CF78C」 Beaver Game

题意

一场博弈游戏，有 \(n\) 个长度为 \(m\) 木棍。两人轮流进行操作，每次操作可选择一根木棒把它进行任意等分，使得分完后每段长度都小于 \(k\)。最终无法操作的人判负。

两人都执行最优操作，先手名为 Timur，后手名为 Marsel，输出最终赢家。

分析

可以分为两种情况：

1. \(n\) 为偶数，此时无论先手怎么分，后手都可以进行同样操作，先手必败。
2. \(n\) 为奇数，则先手需把多出来的一根分完，从而转换为第一种情况的后手，此时先手必胜，否则先手必败。

对于一根木棍，因为是等分，所以最多分成 \(\sqrt m\) 份，然后进行 \(O(1)\) 判断。

总时间复杂度 \(O(\sqrt m)\)。

Code

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline ll read(){ll x=0,f=1;char c=getchar();while(c<48||c>57){if(c==45)f=0;c=getchar();}while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}
ll n,m,k;
signed main(){
    n=read(),m=read(),k=read();
    if(!(n&1))puts("Marsel"),exit(0);//n为偶数
    for(ll i=1;i*i<=m;++i){
        if(m%i)continue;//无法等分成n/i份
        if(i>=k&&m/i>1||i!=1&&m/i>=k)puts("Timur"),exit(0);//i为每份长度或i为份数
    }
    puts("Marsel");//先手必败
    return 0;
}