Josephus问题(Ⅲ)

题目描述

n个人排成一圈，按顺时针方向依次编号1，2，3…n。从编号为1的人开始顺时针"一二三...."报数，报到m的人退出圈子。这样不断循环下去，圈子里的人将不断减少。最终一定会剩下一个人。试问最后剩下的人的编号。

本题的数据规模更具有挑战性，尝试更通用且高效的算法。

输入

不超过1000组数据。

每组数据一行，每行两个正整数，代表人数n (1 <= n < 231)和m(1<=m<=1000)。

输出

每组输入数据输出一行, 仅包含一个整数，代表最后剩下的人的编号。

样例输入

7 2

2 2

样例输出

7

1

解决方案

点击查看代码

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

using namespace std;

typedef long long ll;

int main()

{

    ll n,m,i;

    while(scanf("%lld%lld",&n,&m)!=EOF)

    {

        ll r=0,x;

        if(m==1)

        {

            cout<<n<<endl;

        }

        else

        {

            for(i=2; i<=n; i++)

            {

                if(r+m<i)

                {

                    x=(i-r)/m;

                    if(i+x<n)

                    {

                        i+=x;

                        r=r+x*m;

                    }else

                    {

                        r=r+(n-i)*m;

                        i=n;

                    }

                }

                r=(r+m)%i;

            }

            cout<<r+1<<endl;

        }

    }

    return 0;

}

巴特西

Josephus问题(Ⅲ)

题目描述

输入

输出

样例输入

样例输出

解决方案

最新文章

热门文章