Flavius Josephus Reloaded

Flavius Josephus once was trapped in a cave together with his comrade soldiers surrounded by Romans. All of Josephus' fellow soldiers preferred not to surrender but to commit suicide. So they all formed a circle and agreed on a number k. Every k-th person in the circle would then commit suicide. However, Josephus had different priorities and didn't want to die just yet. According to the legend he managed to find the safe spot in the circle where he would be the last one to commit suicide. He surrendered to the Romans and became a citizen of Rome a few years later.

It is a lesser known fact that the souls of Josephus and his comrades were all born again in modern times. Obviously Josephus and his reborn fellow soldiers wanted to avoid a similar fiasco in the future. Thus they asked a consulting company to work out a better decision scheme. The company came up with the following scheme:

For the sake of tradition all soldiers should stand in a circle. This way a number between 0 and N-1 is assigned to each soldier, where N is the number of soldiers.
As changing numbers in the old scheme turned out to be horribly inefficient, the number assigned to a soldier will not change throughout the game.
The consulting company will provide two numbers a and b which will be used to calculate the number of the next soldier as follows: Let x be the number of the current soldier, then the number of the next soldier is the remainder of a·x² + b mod N.
We start with the soldier with number 0 and each soldier calculates the number of the next soldier according to the formula above.
As everyone deserves a second chance a soldier will commit suicide once his number is calculated for the second time.
In the event that the number of a soldier is calculated for the third time the game will end and all remaining soldiers will surrender.

You are to write a program that given the number of soldiers N and the constants a and b determines the number of survivors.

Input Specification

The input consists of several test cases. Each test case consists of a single line containing the three integers N (2 ≤ N ≤ 10⁹), a and b (0 ≤ a,b < N) separated by white space. You may safely assume that the first soldier dies after no more than one million (10⁶) steps. The input is terminated by a single number 0 which should not be processed.

Output Specification

For each test case output a single line containing the number of soldiers that survive.

Sample Input

2 1 1
5 1 1
10 3 7
101 9 2
698253463 1 181945480
1000000000 999999999 999999999
0

Sample Output

以前的我很笨，用了 O(nlogn) 的方式去找循環。

#include <stdio.h>
#include <map>
#include <iostream>
using namespace std;

int main() {
    long long n, a, b;
    while(scanf("%lld %lld %lld", &n, &a, &b) == 3) {
        map<int, int> COUNT;
        long long next = 0;
        int ret = n;
        while(true) {
            next = (a*(next*next%n)%n + b)%n;
            int &v = COUNT[next];
            v++;
            if(v == 2) ret--;
            if(v == 3) break;
        }
        printf("%d\n", ret);
    }
    return 0;
}

以下的方法比較聰明些。
用跑步的方式去進行，一定會產生環，那麼雖然一開始沒有環，
但最後會進入環中去賽跑，因此就可以用 O(n) 去讓他在環中追到。

一個人一次跑一步，另一個人一次跑兩步，後者會先到環中。
然後當前者碰到後者時，可知道此點在環中了。

#include <stdio.h>

int main() {
    long long n, a, b;
    while(scanf("%lld %lld %lld", &n, &a, &b) == 3) {
        long long next1 = 0, next2 = 0;
        int ret = n;
        while(true) {
            next1 = (a*(next1*next1%n)%n + b)%n;
            next2 = (a*(next2*next2%n)%n + b)%n;
            next2 = (a*(next2*next2%n)%n + b)%n;
            if(next2 == next1)
                break;
        }
        do {
            next1 = (a*(next1*next1%n)%n + b)%n;
            ret--;
        } while(next1 != next2);
        printf("%d\n", ret);
    }
    return 0;
}

我要檢舉

#11053#Flavius Josephus Reloaded

台長： Morris

您可能對以下文章有興趣

[UVA] 1195 - Calling Extraterrestrial Intelligence Again

[UVA][maxflow、黑白染色] 10349 - Antenna Placement

[UVA] 517 - Word

[UVA][dp] 12034 - Race

人氣(1,411) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][循環] 12464 - Professor Lazy, Ph.D.
此分類上一篇:[UVA][窮舉] 12249 - Overlapping Scenes

回應(0)