The 16-th BIT Campus Programming Contest - Online Round--Easy Nim

The 16-th BIT Campus Programming Contest - Online Round--Easy Nim

Problem - C - Codeforceshttps://codeforces.com/gym/103401/problem/C题目大意为每人每轮最多拿m张牌，谁先取完n张牌谁胜；后手有k张魔法牌，每张魔法牌上写有数字（这里把数字放在c数组里）可以将修改上限变为牌上的数字，发动魔法牌时不能取牌。

拿牌（取石子游戏）有一个必胜策略是将n张牌的剩余个数拿到（m+1）的倍数

（先手不能发动魔法牌，所以只是个无情的拿（m+1）的倍数的机器人）

例如：10张牌，每人最多拿3张，这样的话先手必胜，下面的过程着重看先手拿剩几张牌

先手拿1张，剩余9张，后手拿3张，剩余6张；

先手拿2张，剩余4张，后手拿1张，剩余3张；

先手拿3张，剩余0张，先手获胜；

先手的赢面很大，除了n=（m+1）的倍数，后手必胜的情况。

回到这道题，

        显然，当m>=n时，先手必胜；

        当n=（m+1）的倍数，后手必胜的情况时，先手不能发动魔法牌，所以不能扭转局面，于是先手必败；

        当n！=（m+1）时，先手拿牌拿到n=n-n%（m-1），这时后手有两种情况获胜。

        第一种是魔法牌中有（m+1）的倍数刚好是(c[i]+1)的倍数，后手发动牌技能（同时n>c[i]），这样就后手必胜了，也就是说判断条件为只要n大于（c[i]+1）和（m+1）的最小公倍数，那么无论先手怎么取，后手都能控制到（c[i]+1）的倍数；

if(n>(c[i]+1)*(m+1)/__gcd(c[i]+1,m+1)){
    cout<<"zyw";
}

        第二种是魔法牌的组合，魔法牌中有（c[i]+1）的倍数刚好是(c[j]+1)的倍数，后手先发动c[i](n>c[i])，之后n=n-n%(c[i]+1)，这时n是c[i]+1的倍数，然后后手发动c[j]（n>c[j]），如果这时n也是c[j]+1的倍数，那么后手就获胜。

if((c[i]+1)*(c[j]+1)/__gcd(c[i]+1,c[j]+1)<=(n-min(n%(c[i]+1),n%(c[j]+1)))){
    cout<<"zyw";
}

如果这些情况都没有，那么先手必胜。