Mathematical solution of Joseph Ring

subject

【 Joseph ring 】

this n Number in a circle , From numbers 0 Start , Delete the... From this circle every time m A digital . Find the last number left in the circle .

for example ,0,1,2,3,4 this 5 Numbers make a circle , From numbers 0 Start deleting the 3 A digital , Before deleting 4 The numbers in turn are 2,0,4,1, So the last remaining number is 3.

Mathematical method derivation

Solve the Joseph Ring problem , We use backward push , Push us down ： The last remaining number , Position in the first array .

The last number left （ abbreviation “ it ”） When , The total number is 1, Its subscript pos = 0.
So it was safe in the last round , The total number is 2, Its subscript (0+m)%2;

（ explain ： In the last round , The number in front of it （ That is, the red number , Subscript to be m-1） It was removed ; So its subscript is m; Because it's a ring , Therefore need %2）

Then it is safe on the last wheel , The total number is 3, Its subscript ((0+m)%2+m)%3;
Then it is safe to go on the upper wheel , The total number is 4, Its subscript (((0+m)%2+m)%3+m)%4;
…
So it is safe in the first round of the game , The total number is n, Its subscript pos That's what I'm looking for .
That is, if you push back from the bottom up ： If the subscript of its next round is pos, Then the subscript of the current round is ：(pos+m)% Number of people in the current round .

Last , Because the number given is nums = 0,1,2,…,n-1, namely nums[i] = i, So find the subscript [ The formula ] It's equivalent to finding this number .

Solve the code of Joseph Ring

#include<iostream>
#include<list>
using namespace std;

int main(){
    
    int m,n;
    cin >> n >> m;
    int idx = 0;
    for(int i = 2; i <= n; ++i){
    
        idx = (idx + m)% i;
    }
    cout << idx + 1 << endl;
    return 0;
}

Advanced application of this mathematical method

【 Counting game 】100 A circle of individuals , Everyone has a code , Number from 1 Start to 100. They come from 1 Start counting in turn , Check in as M People automatically quit the circle , Then the next person goes from 1 Start counting , Until the remaining number is less than M. What is the original number of the last remaining people ？

#include<iostream>
#include<vector>
using namespace std;

int main(){
    
    int m;
    cin >> m;
    vector<int> cap(m - 1,0);
    for(int i = 0; i < m - 1;++i){
    
        cap[i] = i;
    }
    for(int i = m; i <= 100; ++i){
    
        for(int j = 0; j < m - 1; ++j){
    
            cap[j] = (cap[j] + m) % i;
        }
    }
    for(int i = 0; i < m - 1; ++i){
    
        cout << cap[i] + 1 << endl;
    }
    return 0;
}