Phù thủy và những con số

Điểm: 8,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Trên bảng có hai số nguyên không âm $a$ và $b$ . Hai người chơi lần lượt thực hiện nước đi; người chơi không thể đi sẽ thua. Để cho gọn, ta luôn coi $a \leq b$ (vai trò của hai số là đối xứng — luật vẫn áp dụng tương tự khi $a > b$ ).

Trong mỗi lượt, người đang đi được chọn một trong hai phép biến đổi sau:

Thay $b$ bởi $b - a^{k}$ , với $k$ là số nguyên dương do người chơi tự chọn, miễn là $a^{k} \leq b$ (tức $b - a^{k} \geq 0$ ). Lưu ý đây là lũy thừa $a^{k}$ , không phải tích $a \cdot k$ .
Thay $b$ bởi $b mod a$ .

Nếu sau nước đi $a > b$ thì luật vẫn được áp dụng cho cặp đã sắp xếp lại (số nhỏ hơn đóng vai trò $a$ ).

Nếu một trong hai số bằng $0$ , người đang đi không có nước hợp lệ (không thể lấy phần dư theo $0$ , và phép trừ với cơ số $0$ không sinh ra giá trị mới) — người đó thua.

Giả sử cả hai cùng chơi tối ưu, hãy xác định ai thắng.

Dữ liệu vào

Dòng đầu chứa một số nguyên $t$ — số lượng truy vấn.
$t$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ .

Dữ liệu ra

Với mỗi truy vấn, in ra một dòng duy nhất:

First nếu người đi trước thắng.
Second nếu người đi sau thắng.

Ràng buộc

$1 \leq t \leq 10^{4}$ .
$0 \leq a, b \leq 10^{18}$ .

Ví dụ

Input	Output	Giải thích
4 10 21 31 10 0 1 10 30	First Second Second First	Truy vấn 1: từ $(10, 21)$ người đi trước chuyển sang $(10, 11)$ (trừ $10^{1} = 10$ ). Đối thủ chỉ có thể đi tiếp tới $(10, 1)$ , sau đó người đi trước lấy $10 mod 1 = 0$ và thắng. Truy vấn 2: từ $(10, 31)$ chỉ có hai trạng thái kế tiếp là $(10, 21)$ và $(10, 1)$ — cả hai đều là trạng thái thắng của đối thủ. Truy vấn 3: cặp $(0, 1)$ không có nước đi nên người đi trước thua. Truy vấn 4: từ $(10, 30)$ lấy $30 mod 10 = 0$ , đối thủ rơi vào $(10, 0)$ và không đi được.
1 576460752303423487 2	First	Với cặp số rất lớn, hai bên vẫn chơi tối ưu theo cùng luật; ở đây người đi trước có chiến lược thắng.

Bình luận

Không có bình luận tại thời điểm này.