TopCoder

Thumb 100
WillyPillow
↑我的 username 是綠的。

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

63.1% (41/65)

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

3 6 9

Sample Output

8816390626749971908

Hints

這個偽隨機數產生器的確還蠻隨機的。(事實上,這是xxHash的簡化版。)

Problem Source

Problem set by Yihda Yol

Subtasks

For Testdata: 0 ~ 1, Score: 5
For Testdata: 0 ~ 2, Score: 10
For Testdata: 0 ~ 3, Score: 10
For Testdata: 0 ~ 4, Score: 10
For Testdata: 0 ~ 5, Score: 10
For Testdata: 0 ~ 6, Score: 10
For Testdata: 0 ~ 7, Score: 10
For Testdata: 0 ~ 8, Score: 15
For Testdata: 0 ~ 10, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 500 32768 65536
1 500 32768 65536
2 500 32768 65536
3 500 32768 65536
4 500 32768 65536
5 500 32768 65536
6 800 32768 65536
7 1500 32768 65536
8 4500 32768 65536
9 9500 32768 65536
10 9500 32768 65536