1073 Joseph Ring

benchmark time limit: 1 second space limit: 131072 kb score: 0Difficulty: Basic Questions

Favorites

Follow

2 numbers n and k, indicating n individuals, count to k. (2 <= n, k <= 10^6)

The number of people left last left

3 2

3

It feels that mathematical problems are so difficult …

The

analysis process is like this. Assuming that the first round is eliminated by the person number K-1 (the number starts from 0), then there will be a mapping relationship between the first and second rounds.

k —————–>0

k+1————–>1

…

n-1—————>n-k-1

0——————>n-k

…

k-2 ——————–> N-2 (the first round on the left, the second round on the right)

Set x as the number in the second round. According to the mapping above, there will be such a relationship (x+k)%n. The reason why N-1 individuals were mapped from the second round to the first round of N individuals.

and k = m%n, and the formula can be obtained (x+m)%n.

and pushing this way, from the second round to the third round, it is (x+m)%(n-1), so that it is recursor to the end.

I can think of the last round, there is only one person left, then he is the winner, the number is 0.

So according to the above relationship, push back, get the last round of the number 0 number in the first round, is the answer.

#include <iostream>
#include <cstdio>
#include <cstring>
#define  MAX_N 1000005
using namespace std;
int main()
{
    int n,k;
    int f[MAX_N];
    while(cin>>n>>k)
    {
        f[1]=0;
        for(int i=2;i<=n;i++)
        {
            f[i]=(f[i-1]+k)%i;
        }
        printf("%d\n",f[n]+1);
    }
    return 0;
}