回分類題庫
d048: 2.虛擬亂數產生器
關鍵字: 100年彰雲嘉區複賽

測資點 : 8 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 92 Times / 91 Users | Submit : 215 Times / 95 Users | Accepted rate : 96%
題目加入時間 : 2012-07-06 14:46

Content: 简体中文

Blum Blum Shub (B.B.S.)為一種虛擬亂數產生器(pseudorandom number generator),由三位學者 Lenore Blum,Manuel Blum與Michael Shub於1986年提出。其運作程序如下:首先給定兩個大質數P和Q,這兩個質數除以4之後都要餘3,也就是說 (P mod 4)=(Q mod 4)=3。先令N=P×Q,另給定一個數S,S為大於1之整數且與N互質(或使得P和Q都不是S的因數)。再採用以下之方法來產生8個位元:

N=P×Q
X0=S2 mod N
For i = 1 to 8
    Xi=Xi-12 mod N
    Bi=Xi mod 2
End for

因此,每一回合都會產生一個0或1的一個位元Bi,請將此位元串由左至右排成陣列並轉換成16進位數字輸出。假設輸入P = 11,Q = 7,S = 3,計算出N=77;則

X0=32 mod 77 =9;
X1=92 mod 77=4, B1= 4 mod 2=0, 輸出0;
X2=42mod 77=16, B2= 16 mod 2=0, 輸出0;
X3=162mod 77=25, B3= 25 mod 2=1, 輸出1;
X4=252mod 77=9, B4= 9 mod 2=1, 輸出1;
X5=92mod 77=4, B5= 4 mod 2=0, 輸出0;
X6=42mod 77=16, B6= 16 mod 2=0, 輸出0;
X7=162mod 77=25, B7= 25 mod 2=1, 輸出1;
X8=252mod 77=9, B8= 9 mod 2=1, 輸出1;

故輸出由左至右排列之二進位數為00110011,轉換後之十六進位數為33。

Input:

由鍵盤輸入三個整數 P, Q, S (兩個整數間以一個空白字元區隔)

Output:

請輸出長度為8的二進位數字與轉換後的16進位數字

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
輸入1:
11 7 3

輸入2:
383 503 101355

輸入3:
11 19 32

Sample Output :

輸出1:
00110011 = 33

輸出2:
11001110 = CE

輸出3:
11101011 = EB

Hint :

註1:最後一組測資 N=P×Q 的值可能會超過 int 的範圍,請使用 unsigned long long int。

註2:16進位輸出可使用 cout << hex << uppercase 的寫法。

Author :

100年彰雲嘉區複賽 (管理員:sagit)

  Solve it!   Status Forum