约瑟夫问题――历史的真相

你1定听说过约瑟夫问题，或它的“变种”――猴子选大王等故事吧。但是，你知道约瑟夫问题的历史真相吗？约瑟夫是公元1世纪著名的历史学家。在罗马人占据乔塔帕特后，39 个犹太人与约瑟夫及他的朋友躲到1个洞中，39个犹太人决定宁愿死也不要被敌人俘虏，因而决定了1个流传千古的自杀方式，41个人排成1个圆圈，由第1个人开始报数，每报到第3人该人就必须自杀，然后再由下1个人重新报数，直到所有人都自杀身亡为止。但是约瑟夫和他的朋友其实不想遵从这个约定，约瑟夫要他的朋友先伪装遵从，他将朋友与自己安排在第16个和第31个位置，因而逃过了这场死亡游戏。 现在我们把问题1般化，假定有n（n≥3且n≤100）个人，按1，2，．．．n编号围坐1圈，从1号开始按1，2．．．，m报数，凡报m号的退出到圈外，如此循环报数直到圈内剩下2个人。请问，这两个人的编号是多少？为了更好地感同身受，你可以假定你和你的朋友（最好是你心仪已久的人，这样效果会更好）就在这n个人里面，面临当年约瑟夫一样的问题，所以你应当效法于约瑟夫，赶快想办法和你的朋友逃诞生天。

第1行动1个整数t，表示有多组测试数据。接下来有t行，每行2个整数n和m，空格隔开。

对每组测试数据，输出最后剩下的两个人的编号，按从小到大输出，以空格隔开，占1行。

2
3 2
5 4

1 3 
1 2 
#include <iostream> 
using namespace std; 
int main() 
{ 
    int n,m,a[110],i,j,k,t; 
    cin >> t;  
    while(t--) 
    { 
        cin >> n >> m; 
        for(i=0;i<n;i++) 
        { 
            a[i]=1; 
        } 
        i=0; 
        k=0; 
        j=0; 
        while(n-j>2) 
        { 
            if(a[i]!=0) 
            { 
                k++; 
            } 
            if(k==m) 
            { 
                a[i]=0; 
                j++; 
                k=0; 
            } 
            if(i==n⑴) 
            { 
                i=0; 
            } 
            else
            { 
                i++; 
            } 
        } 
        for(i=0;i<n;i++) 
        { 
            if(a[i]==1) 
            { 
                cout << i+1 << " " ; 
            } 
        } 
        cout << endl; 
    } 
    return 0; 
}