HDU 3951 Coin Game

Description:

After hh has learned how to play Nim game, he begins to try another coin game which seems much easier.

The game goes like this:
Two players start the game with a circle of n coins.
They take coins from the circle in turn and every time they could take 1~K continuous coins.
(imagining that ten coins numbered from 1 to 10 and K equal to 3, since 1 and 10 are continuous, you could take away the continuous 10 , 1 , 2 , but if 2 was taken away, you couldn’t take 1, 3, 4, because 1 and 3 aren’t continuous)
The player who takes the last coin wins the game.
Suppose that those two players always take the best moves and never make mistakes.
Your job is to find out who will definitely win the game.

Input:

The first line is a number T(1<=T<=100), represents the number of case. The next T blocks follow each indicates a case.
Each case contains two integers N(3<=N<=109,1<=K<=10).

Output:

For each case, output the number of case and the winner “first” or “second”.(as shown in the sample output)

Sample Input:

2
3 1
3 2

Sample Output:

Case 1: first
Case 2: second

题目链接

环上n个点，每次只能取任意1~k个连续点(环不会自动连接)，取走最后一个点胜，求先手胜还是后手胜。

首先若k=1，则双方每次只能拿取一个点，所以若n为奇数则先首胜，若n为偶数则后手胜；

若k≠1，若k≥n则先手方可以一次拿完，则先手方胜，若k<n则先手方会将环切断变为一条链，后手方只需将此链分为两条数目相同的小链即可保证游戏胜利(先手方怎么拿后手方就跟着怎么拿)，所以后手方胜。

AC代码:

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char *argv[]) {
    int T;
    scanf("%d", &T);
    for (int Case = 1, N, K; Case <= T; ++Case) {
        scanf("%d%d", &N, &K);
        printf("Case %d: ", Case);
        if (K == 1) {
            if (N & 1) {
                printf("first\n");
            }
            else {
                printf("second\n");
            }
        }
        else {
            if (N <= K) {
                printf("first\n");
            }
            else {
                printf("second\n");
            }
        }
    }
    return 0;
}