TopCoder

Adrien Wu
AC×29New TIOJ ?

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,A0,B0的值,且:
1. C0=0
2. Ai+1=PRNG(Bi,gcd(Ai,Bi))
3. Bi+1=PRNG(Ai+1,gcd(Ai,Bi))
4. Ci+1=PRNG(Ci,gcd(Ai,Bi))
請計算CN

Input Format

輸入有三個以空白隔開的非負整數N,A0,B0

對於所有測資,N3×107A,B2641
保證對於所有0i<NAi0,Bi0

Output Format

請輸出CN

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