围圈报数问题的一种算法的原理解析

围圈报数问题描述如下：
有n个人围成一圈，依次编号为0,1,2,3......,然后从0开始报数,每次报数为M的倍数的人出圈,后面的人继续报数,如此循环,求最后一个留在圈子里的人的编号。
在一篇博客里看到一个比较diao的解法：

#include <stdio.h> 

int M = 3; 

int main() 
{ 
    int n, s = 0; 
    scanf("%d", &n); 
    for (int i = 2; i <= n; ++i) 
        s = (s+M)%i; 
    printf("%d\n", s+1); 
    return 0; 
}

其实思路很明显，就是逆推出队的过程。
其中s表示的是在每个逆推阶段时最后一个人在圆圈中所在的位置。
M即为出队计数，比如3，则每数到3或3的倍数就出队。
假设只剩i+1个人的时候报数报到了第j个，那么下一次出队的就是(j + M)%(i + 1)
假设只剩i个人的时候报数报到了第k个，那么下一次出队的就是(k + M)%i
以此类推......
如果把每次报数后剩下的成员从出队者之后开始重新从0编号，那么显然可以从i个人时的编号倒推出i+1个人时的编号，所以有s=(s+M)%(i+1)，且i∈[1, n－1]，又因为最后一个人的编号必然是0，所以通过递推求解即可。