2059 . 大陸人系列3：偽隨機最大公因數（PRGCD）
TopCoder
Tags
Description
又到了久違的大陸人GCD時間了！
給你$N$對由偽隨機數產生器產生的正整數，請計算出這$N$對數字的最大公因數分別是多少。
具體來說，有一個偽隨機數產生器函數PRNG(a,b)長得像這樣：
#include <cstdint> uint64_t PRNG(uint64_t a, uint64_t b) { static const uint64_t table[3] = {0x9e3779b185ebca87, 0xc2b2ae3d27d4eb4f, 0x165667b19e3779f9}; auto Mix = [](uint64_t a, uint64_t b) { a += b * table[1]; a = (a << 31) | (a >> 33); return a * table[0]; }; uint64_t v1 = Mix(-table[0], a); uint64_t v2 = Mix(table[1], b); uint64_t ret = ((v1 << 18) | (v1 >> 46)) + ((v2 << 7) | (v2 >> 57)); ret ^= ret >> 33; ret *= table[1]; ret ^= ret >> 29; ret *= table[2]; ret ^= ret >> 32; return ret; }
已知$N,A_0,B_0$的值，且：
1. $C_0=0$
2. $A_{i+1}=\text{PRNG}(B_i,\text{gcd}(A_i,B_i))$
3. $B_{i+1}=\text{PRNG}(A_{i+1},\text{gcd}(A_i,B_i))$
4. $C_{i+1}=\text{PRNG}(C_i,\text{gcd}(A_i,B_i))$
請計算$C_N$。
Input Format
輸入有三個以空白隔開的非負整數$N,A_0,B_0$。
對於所有測資，$N\leq 3\times 10^ 7$，$A,B\leq 2^ {64}-1$。
保證對於所有$0\leq i<N$，$A_i\neq 0, B_i\neq 0$。
Output Format
請輸出$C_N$。
Sample Input 1
3 6 9
Sample Output 1
8816390626749971908
Hints
這個偽隨機數產生器的確還蠻隨機的。（事實上，這是xxHash的簡化版。）
Problem Source
Problem set by Yihda Yol
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~1 | 5 |
| 2 | 0~2 | 10 |
| 3 | 0~3 | 10 |
| 4 | 0~4 | 10 |
| 5 | 0~5 | 10 |
| 6 | 0~6 | 10 |
| 7 | 0~7 | 10 |
| 8 | 0~8 | 15 |
| 9 | 0~10 | 20 |