TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

46.2% (6/13)

Tags

Description

本題需要使用給定的亂數產生器,請以以下的格式送出解答。

#include <iostream>
using namespace std;

unsigned LFSR() {
  static unsigned short lfsr = 44257;
  unsigned bit = ((lfsr >> 0) ^   (lfsr >> 2) ^   (lfsr >> 3) ^   (lfsr >> 5) ) & 1;
  return lfsr =  (lfsr >> 1) | (bit << 15);
}

int main () {
    // your code
}

呼叫 LFSR() 會回傳一個題目需要的亂數。
ex: int num = LFSR();


題目本身

在現實世界中,有很多是透過電腦生成的亂數來做事情的,最常見的例如虛擬賭場。到這裡如果你足夠聰明,你就會發現一件事情:只要你能夠知道它的亂數生成方式,以及它現在生成出哪些數字,你就可以完美預測之後的數字。因此這題的題目是:我們已經知道某個亂數生成器是利用我們上面所寫的函式 LFSR() 來產生出 0 到 n(包括 0 和 n),且不能被 k 整除(包括 0)的亂數。

知道這件事情的你,能夠預測這個亂數生成器產生出來的前五個亂數為何嗎?

提示

如果你看不懂上面的題目,可以參考下面的流程圖。

範例測資解說

  • 如果題目輸入 $n = 4, k = 3$,那麼我們依序呼叫 LFSR() 所產生出來的序列會長的像下面這樣子:

    • 22128 → 43832 → 21916 → 10958 → 5479 → 35507 → 17753 → 8876 → 37206。
  • 如果我們把所有數字都對 $(n+1)$ 取餘數,得到的生成序列會長的像下面這樣子:

    • 3 → 2 → 1 → 3 → 4 → 2 → 3 → 1 → 1
  • 我們在挑出符合條件的,也就是不能夠被 $k$ 整除的:

    • 3 → 21 → 3 → 42 → 3 → 1 → 1
  • 因此,答案輸出為 2 1 4 2 1每個數字後接需附加換行

Input Format

輸入只有一行,裡面有兩個數字 $n, k$,代表題目所說的 $n, k$。

  • $1 \le n, k \le 65535$,且保證輸出一定會停止。

Output Format

輸出題目所說的偽亂數生成器產生出來的前五個數字,一行一個。

Sample Input 1

4 3

Sample Output 1

2
1
4
2
1

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~8 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2