2059 . 大陸人系列3：偽隨機最大公因數（PRGCD）

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

34.8% (8/23)

Submission's AC Ratio

11.3% (40/353)

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 500 32768 262144 1 2 3 4 5 6 7 8 9
1 500 32768 262144 1 2 3 4 5 6 7 8 9
2 500 32768 262144 2 3 4 5 6 7 8 9
3 500 32768 262144 3 4 5 6 7 8 9
4 500 32768 262144 4 5 6 7 8 9
5 500 32768 262144 5 6 7 8 9
6 800 32768 262144 6 7 8 9
7 1500 32768 262144 7 8 9
8 4500 32768 262144 8 9
9 9500 32768 262144 9
10 9500 32768 262144 9
Submit
Back to Top