Fork me on GitHub

程序设计竞赛:约瑟夫环plus

发表于 | 分类于 | | 次阅读
考虑经典的约瑟夫环模型：n个人按顺序围成一圈，从第一个人开始报数，从1开始报，报到k这个数的人会被移出去，然后下一个人从1开始重新报数，第n个人报完数之后第1个人接着报数，问整个过程中第1个人报了几次数。

Problem C. 约瑟夫环plus

时间限制 2000 ms
内存限制 64 MB

题目描述

考虑经典的约瑟夫环模型：n个人按顺序围成一圈，从第一个人开始报数，从1开始报，报到k这个数的人会被移出去，然后下一个人从1开始重新报数，第n个人报完数之后第1个人接着报数，问整个过程中第1个人报了几次数。

输入数据

两个正整数n，k
1 <= n <= 1000000000000000000
1 <= k <= 200

输出数据

第1个人被移除之前一共报了几次数

样例输入

1
4 4

样例输出

1
3

样例说明

注意n需要用long long存

题解

cur_number存储第一个人每次轮到他时所报的号，最开始时，第一个人报号的次数res为1，cur_number也为1；从上一次这个人报号到下一次轮到他报号为止为一个周期，在这个周期内有(n + cur_number) / k个人被移出去，这个人报的号更新为(n + cur_number) % k；所以当(n + cur_number) % k = 0时，第一个人会被移出去，也就是下一次轮到他时cur_number = 0。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

long long n, k, cur_number, res, temp;

int main() {
    cin >> n >> k;
    res = 1;
    cur_number = 1;
    while (cur_number != 0) {
        temp = n + cur_number;
        n -= temp / k;
        cur_number = temp % k;
        res++;
    }
    cout << res << endl;
    return 0;
}
0%