TopCoder

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

User's AC Ratio

77.8% (7/9)

Submission's AC Ratio

44.3% (27/61)

Description

  我們有一個無限大的$xy$平面和一台神奇的發球機器,對任何整數$a,b,c,d$,只要我們將發球機器置於點$(a,b)$(其中$(a,b)$表示$x$座標為$a$且$y$座標為$b$的點),並設定發球機器將球拋至點$(c,d)$,則發球機器會拋出一顆球至點$(c,d)$,接著該球會反彈至點$(ac-bd,bc+ad)$並固著於點$(ac-bd,bc+ad)$上,從此不再移動。我們只允許將發球機器置於$x$座標和$y$座標都是整數的點上。
  愛麗絲想要讓六顆球分別固著於點$(a_1,b_1),(a_2,b_2),(a_3,b_3),(a_4,b_4),(a_5,b_5),(a_6,b_6)$上,其中對所有$i\in\{1,2,3,4,5,6\}$,$a_i,b_i$都是整數且$(a_i,b_i)\neq(0,0)$。但她希望發球機器始終都在同一個點上,也就是她要找到一個置放發球機器的點$(p,q)$(其中$p,q$都是整數),使得對所有$i\in\{1,2,3,4,5,6\}$,皆存在$x$座標與$y$座標都是整數的點$(c_i,d_i)$,滿足 $(pc_i-qd_i,qc_i+pd_i)=(a_i,b_i)$,如果滿足上述條件的點很多,則愛麗絲要選擇其中距離原點$(0, 0)$最遠的一個點作為$(p,q)$,並將發球機器置於該點$(p,q)$,然後告訴稻草人$|p|+|q|$的值。
  給定$a_1,b_1,a_2,b_2,a_3,b_3,a_4,b_4,a_5,b_5,a_6,b_6$,請算出稻草人被告知的值。

實際模考中未提供__int128型別。

Input Format

對所有$i\in\{1,2,3,4,5,6\}$,測資的第$i$行為$a_i$和$b_i$(兩數間以空白區隔)。

子任務(測資) 額外限制 分數
1 (0~4) $|a_i|, |b_i|\leq 10$ 6
2 (0~9) $|a_i|, |b_i|\leq 100$ 13
3 (0~14) $|a_i|, |b_i|\leq 1000$ 35
4 (0~19) $|a_i|, |b_i|\leq 10^ 9$ 43
5 (0~26) $|a_i|, |b_i|\leq 10^ {15}$ 3

Output Format

請輸出稻草人被告知的值。

Sample Input

#Sample Input 1
-60 40
-4 32
-28 -16
-68 4
-100 -20
12 64
#Sample Input 2
24 -31
27 -24
31 -34
36 -32
38 -37
-17 -59
#Sample Input 3
4 9
22 -8
13 4
55 100
66 4
44 -7
#Sample Input 4
12 -99
33 -81
39 -88
13 -1
62 41
68 34
#Sample Input 5
81 100
100 99
34 56
-3 -87
-15 24
26 27
#Sample Input 6
24 -31
27 -24
31 -34
36 -32
38 -37
-17 -59

Sample Output

#Sample Output 1
12
#Sample Output 2
7
#Sample Output 3
1
#Sample Output 4
13
#Sample Output 5
1
#Sample Output 6
7

Hints

Problem Source

題目取自2017 TOI選訓第四次模擬考pD

Subtasks

No. Testdata Range Score
1 0~4 6
2 0~9 13
3 0~14 35
4 0~19 43
5 0~26 3

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 900 262144 262144 1 2 3 4 5
1 900 262144 262144 1 2 3 4 5
2 900 262144 262144 1 2 3 4 5
3 900 262144 262144 1 2 3 4 5
4 900 262144 262144 1 2 3 4 5
5 900 262144 262144 2 3 4 5
6 900 262144 262144 2 3 4 5
7 900 262144 262144 2 3 4 5
8 900 262144 262144 2 3 4 5
9 900 262144 262144 2 3 4 5
10 900 262144 262144 3 4 5
11 900 262144 262144 3 4 5
12 900 262144 262144 3 4 5
13 900 262144 262144 3 4 5
14 900 262144 262144 3 4 5
15 900 262144 262144 4 5
16 900 262144 262144 4 5
17 900 262144 262144 4 5
18 900 262144 262144 4 5
19 900 262144 262144 4 5
20 900 262144 262144 5
21 900 262144 262144 5
22 900 262144 262144 5
23 900 262144 262144 5
24 900 262144 262144 5
25 900 262144 262144 5
26 900 262144 262144 5