一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到M，凡报到M的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？ （注意：由于该问题规模显著提升，请扩展阅读“约瑟夫环”，理解更好的数学方法求解） 输入格式: 输入在一行中给两个正整数N, M（1<= N,M ≤10000000）。 输出格式: 在一行中输出当选猴王的编号。 用C语言编写代码解决上述问题

以下是使用循环链表的解法，时间复杂度为O(NM)：

#include <stdio.h>
#include <stdlib.h>

typedef struct Monkey {
    int id;             // 猴子的编号
    struct Monkey *next;    // 指向下一个猴子的指针
} Monkey;

// 创建n只猴子构成的循环链表
Monkey *createMonkeys(int n) {
    Monkey *head = NULL, *tail = NULL;
    for (int i = 1; i <= n; i++) {
        Monkey *p = (Monkey *)malloc(sizeof(Monkey));
        p->id = i;
        p->next = NULL;
        if (head == NULL) {
            head = p;
        } else {
            tail->next = p;
        }
        tail = p;
    }
    tail->next = head;  // 将链表首尾相连，形成循环链表
    return head;
}

// 删除第k个猴子，并返回下一个猴子的指针
Monkey *deleteMonkey(Monkey *p, int k) {
    for (int i = 1; i < k; i++) {
        p = p->next;
    }
    Monkey *q = p->next;
    p->next = q->next;
    printf("猴子%d被淘汰\n", q->id);
    free(q);
    return p->next;
}

// 选出新猴王
int selectKing(int n, int m) {
    Monkey *p = createMonkeys(n);
    for (int i = 1; i < n; i++) {
        p = deleteMonkey(p, m);
    }
    int king = p->id;
    free(p);
    return king;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int king = selectKing(n, m);
    printf("新猴王的编号是%d\n", king);
    return 0;
}

由于时间复杂度较高，当N和M较大时，程序可能需要很长时间才能运行完毕。可以使用数学方法进行优化，时间复杂度为O(N)。