取石子游戏 1

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 553 字

一堆共N颗石子，两人轮流取，每次可取1到K颗

一本通
例

正文

/*
原题：T1663「一本通 6.7 例 1」取石子游戏 1
题意：一堆共 N 颗石子，两人轮流取，每次可取 1 到 K 颗，取走最后一颗者胜。
先手必胜输出 1，后手必胜输出 2。
思路：经典的巴什博弈。每一轮两人取的总数可以被控制在 K+1 颗，
因此若 N 是 K+1 的倍数，先手无论怎么取，后手都能补齐到 K+1，后手必胜；
反之先手第一次取走 N%(K+1) 颗，把必败态留给对手，先手必胜。
复杂度：时间 O(1)，空间 O(1)
易错点：1) 判据看的是 N%(K+1)，而不是 N%K；
2) 输出是 1/2 而不是 yes/no，别写反；
3) 取走最后一颗者胜，没有"无法行动者输"以外的规则。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long N,K;
    cin>>N>>K;
    if(N%(K+1)!=0){
        cout<<1<<"\n";
    }else{
        cout<<2<<"\n";
    }
    return 0;
}

取石子游戏 1

正文

一本通·提高篇的其它内容