Codeforces Round #70(Div2 only)

C. Beaver Game

問題概要

n本の棒があり、それぞれの長さはmメートル。それを用いて二人が以下のゲームをする。
棒を一本選び、mの約数xでx等分する。その時の長さはk以上でなければならない。

この操作ができなくなったとき、できなくなったプレイヤーが負けである。
n,m,kが与えられたとき、先手または後手どちらが勝つかを返せ。プレイヤーは二人とも最善をつくすものとする。

方針

切れる棒が0本の時後手必勝。
1本のとき、m/k以下で最大の約数の本数に切ることにより、切れる棒を0本にできる。
すなわち先手必勝。
2本の時は、上を行えば1本にできるので後手必勝。
同様に切れる棒が偶数の時は後手必勝で、奇数の時は先手必勝。

初期状態で切れる棒があるかどうかは、
mが2以上の約数x（ただしm/x>=kを満たす）をもつかどうかにより判定すればいい。

int n,m,k;

void run(){
  cin>>n>>m>>k;
  //mにk<=m/xを満たすような2以上の約数xがある
  if(k==1){
    if(n%2&&m>1)cout<<"Timur"<<endl;
    else cout<<"Marsel"<<endl;
    return;
  }
  for(int i=2;(ll)i*i<=m;i++)if(m%i==0&&(m/i>=k||i>=k)){
      if(n%2)cout<<"Timur"<<endl;
      else cout<<"Marsel"<<endl;
      return;
    }
  cout<<"Marsel"<<endl;
}