TopCoder

User's AC Ratio

100.0% (40/40)

Submission's AC Ratio

39.7% (52/131)

Description

在某個不知名的外星王國中,外星人發展了一套獨特的數字系統與銀河捷運系統。根據科學家的研
究,外星人的數字系統可對應到我們所使用的「模 $M$ 運算」,其中 $M$ 為一個質數。以下用模運算的
術語來描述外星人的數字系統。以 $M = 7$ 為例,下列的算式在外星球的數學系統是成立的:

• 2 × 3 = 6
• 2 × 5 = 3
• 2 + 3 = 5
• 2 + 6 = 1
• 3 − 1 = 2
• 3 − 5 = 5

我們的研究人員還發現了銀河捷運系統與他們的數字系統存在著高度的關聯。首先,銀河捷運系統和我們在地球上常見的直線形軌道或是環形軌道不一樣,外星人自己有一套獨特的站台分佈機制以及捷運運行技術。再來,我們發現銀河捷運系統的每一條路線都可以用一個方程式 $y^ 2 = x^ 3 + ax + b$ 和一質數 $M$ 來表示,而這個方程式上的每個整數點 $(x, y)$ 都分別代表一個這條路線上的站台。以下面這條捷運路線為例:

$$
y^ 2 = x^ 3 − x + 1, M = 13
$$

座標 $(3, 8)$ 是這條路線的站台,因為 $8^ 2 \equiv (3^ 3 - 3 + 1) \equiv 12 \pmod{13}$ 。除此之外, $(0, 1),(1, 1),(3, 5)$ 也是這條路線上的站台。

外星王國中對直線的定義也和我們類似,例如在地球上,我們說三個 $x$ 座標相異 的點 $(x_1, y_1),(x_2, y_2),(x_3, y_3)$ 共線代表他滿足:

$$
\frac{y_1 - y_2}{x_1 - x_2} = \frac{y_2 - y_3}{x_2 - x_3}
$$

雖然我們並不知道外星人是如何做除法的,但我們知道交叉相乘的法則仍然通用。因此外星球中三點共線的條件可以寫成:

$$
(y_1 - y_2)(x_2 - x_3) \equiv (y_2 - y_3)(x_1 - x_2) \pmod M
$$

外星人要搭乘銀河捷運的時候,要先輸入自己所在的站台座標 $(x_1, y_1)$,接著輸入另外一個站台的座標 $(x_2, y_2)$ 作為參考值,並再找出第三個站台座標 $(x_3, y_3)$,使得這三個點共線。這第三站台就是外星人要前往的地方。在給出站台座標 $(x_1, y_1)$ 與參考值站台座標 $(x_2, y_2)$ 的情況下,研究人員告訴我們一個可以求出目的地座標 $(x_3, y_3)$ 的方法:首先我們可以假設一條直線 $y \equiv mx + k \pmod M$ 作為同時通過三個點的直線方程,直線方程式中的斜率 $m$ 可以利用費馬小定理 $x \cdot x ^ {M - 2} \equiv 1 \pmod M$ 得出 $m \equiv (y_2 - y_1) \cdot (x_2 - x_1) ^ {M - 2} \pmod M$ 的結論。接著,將這條直線方程代進捷運路線的方程式可以得到 $(mx + k)^ 2 = x^ 3 + ax + b \pmod M$ 。並且從根與係數的法則可以得出 $x_1 + x_2 + x_3 = m^ 2 \pmod M$ 進而求出目的地的 $x$ 及 $y$ 座標。

給定一條銀河捷運路線的參數 $a, b, M$ 以及外星人的出發站台和中間所有的參考站台之座標,請撰寫一支程式算出最後外星人所抵達站台的座標。

Input Format

輸入第一行有一個正整數 $t$,代表測資的筆數。接下來 $t$ 行每行有 $7$ 個整數 $M, a, b, x_1, y_1, x_2, y_2$。其中 $M$ 為模數,$a$ 和 $b$ 為捷運路線方程式的二參數,$(x_1, y_1)$ 及 $(x_2, y_2)$ 分別為起點及參考點的座標。同一行的兩數字間以一空白分隔。

Output Format

對於每筆測資請輸出一行含兩數字 $x_3, y_3$,以一空白分隔。$x_3$ 與 $y_3$ 皆為 $0$ 以上 $M − 1$ 以下 (包含 $0$ 與 $M − 1$) 的整數,代表外星人將前往的站台座標。

Sample Input

3
13 1 0 4 4 2 7
13 3 1 0 12 6 12
13 3 1 7 12 10 11

Sample Output

6 1
7 12
12 6

Hints

• $1 \leq t \leq 10^ 5$,且 $t$ 為整數。
• $a, b, x_1, y_1, x_2, y_2$ 都是 $0$ 以上 $M − 1$ 以下 (包含 $0$ 與 $M − 1$) 的整數。
• $x_1 \neq x_2$。
• $2 \leq M < 2^ {31}$ ,$M$ 為一質數。
• 保證存在第三個站台 $(x_3, y_3)$,使得 $x_3 \neq x_1$ 且 $x_3 \neq x_2$,並且與 $(x_1, y_1)$ 和 $(x_2, y_2)$ 共線。

本題共有三組測試題組,條件限制如下所示。每一組可有一或多筆測試資料,該組所有測試資料皆需答對才會獲得該組分數。
1. ($36\%$) $t \leq 100, M \leq 100$。
2. ($32\%$) $t \times M \leq 10^ 5$。
3. ($32\%$) 無額外限制。

Problem Source

2020 TOI 入營考
testdata set by Omelet

Subtasks

No. Testdata Range Constraints Score
1 0~9 $t \leq 100, M \leq 100$ 36
2 0~19 $t \times M \leq 10^ 5$ 32
3 0~39 無額外限制 32

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3
1 1000 524288 65536 1 2 3
2 1000 524288 65536 1 2 3
3 1000 524288 65536 1 2 3
4 1000 524288 65536 1 2 3
5 1000 524288 65536 1 2 3
6 1000 524288 65536 1 2 3
7 1000 524288 65536 1 2 3
8 1000 524288 65536 1 2 3
9 1000 524288 65536 1 2 3
10 1000 524288 65536 2 3
11 1000 524288 65536 2 3
12 1000 524288 65536 2 3
13 1000 524288 65536 2 3
14 1000 524288 65536 2 3
15 1000 524288 65536 2 3
16 1000 524288 65536 2 3
17 1000 524288 65536 2 3
18 1000 524288 65536 2 3
19 1000 524288 65536 2 3
20 1000 524288 65536 3
21 1000 524288 65536 3
22 1000 524288 65536 3
23 1000 524288 65536 3
24 1000 524288 65536 3
25 1000 524288 65536 3
26 1000 524288 65536 3
27 1000 524288 65536 3
28 1000 524288 65536 3
29 1000 524288 65536 3
30 1000 524288 65536 3
31 1000 524288 65536 3
32 1000 524288 65536 3
33 1000 524288 65536 3
34 1000 524288 65536 3
35 1000 524288 65536 3
36 1000 524288 65536 3
37 1000 524288 65536 3
38 1000 524288 65536 3
39 1000 524288 65536 3