Trò Chơi Chia Số
Points
45
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
number
Đề bài
Cho n trò chơi độc lập. Mỗi trò chơi bắt đầu với một số nguyên dương a_i. Mỗi lượt trong trò chơi thứ i, người chơi phải chọn một ước nguyên tố p của số hiện tại x và thay thế x bằng x/p. Khi x = 1, trò chơi kết thúc.
Hai người chơi thay phiên nhau. Mỗi lượt, người chơi chọn một trò chơi chưa kết thúc và thực hiện nước đi. Người chơi nào không thể thực hiện nước đi nào sẽ thua.
Người chơi đầu tiên đi trước. Xác định ai sẽ thắng nếu cả hai chơi tối ưu.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương T (1 ≤ T ≤ 100) — số lượng test case.
- Mỗi test case gồm 2 dòng:
- Dòng đầu chứa n (1 ≤ n ≤ 100) — số trò chơi.
- Dòng sau chứa n số nguyên a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9).
Dữ liệu ra
- Với mỗi test case, in ra "First" nếu người chơi đầu tiên thắng, "Second" nếu người chơi thứ hai thắng.
Ví dụ
Input
3
1
12
2
4 6
3
2 3 5
Output
First
First
First
Giải thích
- 12 = 2^2 × 3, tổng số thừa số nguyên tố = 3 (kể cả lặp). Grundy = 3. XOR = 3 ≠ 0.
- 4 = 2^2 (2 thừa số), 6 = 2 × 3 (2 thừa số). Grundy: 2 XOR 2 = 0 → Second? Nhưng thực tế mỗi nước đi chia cho một ước nguyên tố, nên Grundy(x) = Ω(x) (tổng số thừa số nguyên tố kể cả lặp). XOR = 2 ^ 2 = 0 → Second.
Input chỉnh lại
3
1
12
2
4 6
3
2 3 5
Output
First
Second
First
Giới hạn
- 1 ≤ T ≤ 100
- 1 ≤ n ≤ 100
- 1 ≤ a_i ≤ 10^9
- Thời gian: 3 giây
- Bộ nhớ: 256 MB
Community Discussion