首页 > 代码库 > 变形的约瑟夫环问题

变形的约瑟夫环问题

2024-10-23 10:05:01   209人阅读

Problem C: 士兵报数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 142  Solved: 68
[Submit][Status][Web Board]

Description

N个站成一列的士兵和一个整数M，士兵编号是1 --- N。每次士兵按编号从小到大的顺序依次报数，如果报的数不是M的倍数，则该士兵出列。这样重复几次直到剩下的士兵的数量小于M为止。问最后剩下的士兵有几个，他们的编号分别是多少。  

Input

 多组测试数据。

每组数据包含两个数N，M。

N<=1000000000

M<=1000

当n=0,m=0时结束

Output

 每组测试数据输出两行。

第一行一个数t，代表剩下的士兵数。

第二行t个数，代表剩下的士兵的编号，升序排列。

Sample Input

10 3
8 3
0 0

Sample Output

1
9
2
3 6

可以找出规律来:

10 3

红色代表下标

初始化:1 2 3 4 5 6 7 8  9 10

第一次之后:3 6 9

                   1 2 3

第二次之后:9(最后剩下的)

                   1

结束:

8 3

初始话:1 2 3 4 5 6 7 8

第一次之后:3 6

                   1 2

结束


自己多举几个例子可以发现：

最后剩下的数目肯定<m个，并且每一个都是m的倍数，那么我们该怎么找出所有的呢？

<span style="color:#ff0000;"> </span>int cent = n/m;//表示每一个趟有多少个下标是m的倍数
        int count =  1;
        while(cent >= m)//直达满足题意
        {
                 cent = cent/m;
                 count++;//求总共可以报几趟数
        }

然后我们可以根据报了几趟数字求结束时候第一个人的最初下标

int a = 1;
        for(int i = 1; i <=count ;i++)
        {
              a *= m;//每次都乘以m=3,比如报了2趟数，第一次留下3,6,9,12，15,18（现在下标分别是1,2,3,4,5,6），第二趟留下9,18，那么a 最后的值就是1*3*3=9,那就求出了最后剩下的第一个是什么，求出第一个以后，也知道还剩几个，那就很好求了，最后的答案中每个数肯定是第一个数的倍数
        }


完整代码:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
   #ifdef xxz
   freopen("in","r",stdin);
   #endif // xxz
   int n,m;
   while(scanf("%d%d",&n,&m) != EOF && n != 0 && m != 0)
   {
 
        int cent = n/m;
        int count =  1;
        while(cent >= m)
        {
                 cent = cent/m;
                 count++;
        }
        cout<<cent<<endl;
        int a = 1;
        for(int i = 1; i <=count ;i++)
        {
              a *= m;
        }
        for(int i = 1; i <cent; i++)
        {
            cout<<a*i<<" ";
        }
        if(cent != 0 ) cout<<a*cent<<endl;
   }
    return 0;
}






变形的约瑟夫环问题


联系
我们