Nếu bỏ qua phần cốt truyện thì đề bài khá dễ hiểu: Cho trước một số \(n\), hai người chơi lần lượt chia \(n\) cho ước của \(n\) (mà là lũy thừa của một số nguyên tố).

Sau lượt chơi của người \(A\), nếu \(n = 1\) thì \(A\) thắng. Theo nguyên lý của lý thuyết trò chơi: khi các đối thủ đều chơi tối ưu, ta luôn xác định được người thắng, người thua trong mọi trạng thái của trò chơi. Vì thế hoàn toàn có thể thêm một mảng QHĐ để tính chính xác số lượng nước đi tối thiểu/ tối đa.

Subtask 1:

Vì \(n = p^3\) là lũy thừa của SNT nên người đi trước sẽ thắng trong một nước đi.

Vì vậy chỉ cần in ra \(1\). Vấn đề duy nhất là kiểm tra số \(n\) trong input có dạng này không?

\(O(n^{1/3})\)

Subtask 2:

Có \(n = 6^x = 2^x \times 3^x\). Về mặt bản chất, tại mỗi lượt chơi, mỗi người chơi chọn số mũ của \(2\) hoặc \(3\) trong dạng phân tích TSNT của \(n\) và giảm số mũ này xuống giá trị $ \ge 0$ bất kì, nếu số mũ này dương.

Người chơi thứ hai luôn thắng. Chiến thuật chơi của anh ta như sau: sau nước đi của người thứ nhất (đi trước), anh ta chỉ cần giảm đi một lượng tương tự tại số mũ của TSNT khác.
Ví dụ, nếu lượt vừa rồi người đi trước giảm \(2\) đơn vị vào số mũ của \(2\) thì người đi sau sẽ giảm \(2\) đơn vị vào số mũ của \(3\).

Bằng cách này, người đi sau đảm bảo được sau khi mình đi xong thì số mũ của \(2\) và \(3\) bằng nhau. Tại nước đi kế cuối, khi người đi trước giảm một số mũ xuống \(0\) thì người đi sau sẽ giảm số mũ còn lại xuống \(0\) và thắng.

Vì đề bài phát biểu: Người chơi biết mình thua sẽ cố gắng câu giờ hết sức có thể, ngược lại người sẽ thắng muốn trò chơi kết thúc càng sớm càng tốt nên số nước đi sẽ là \(2x\).

\(O(log(n))\)

Subtask 3:

Subtask trên đã gợi ý ta phân tích số \(n\) ra TSNT. Nếu có kiến thức về lý thuyết trò chơi, không khó để nhận thấy đây chính là bài toán Nim-game trên dãy các số mũ.

Tuy nhiên, phần cài đặt thì vô cùng đơn giản, trực tiếp. Không cần biết về Nim hoặc tính chất "Nếu tổng XOR toàn dãy bằng \(0\) thì người đi sau thắng", chỉ cần biết QHĐ, ta vẫn có thể giải được.

Đặt \(f[i] = true/false\) với ý nghĩa là nếu trò chơi bắt đầu với \(n = i\) thì người đi trước thắng hay thua, và mảng \(cnt[i]\) chính là số nước đi để trò chơi đấy kết thúc.

Khởi tạo \(f[1] = 0, cnt[1] = 0\).

Với \(x > 1\), gọi $S = {y : y = p^k, y|x} $ là tập các ước (là lũy thừa số nguyên tố) của \(x\). Ta có:

• Nếu \(f[\frac{x}{y}] = true \forall y\) thì \(f[x] \leftarrow false, cnt[x] = max(cnt[\frac{x}{y}]) + 1\)
• Ngược lại, tồn tại \(f[\frac{x}{y}] = false\) nên \(f[x] \leftarrow true\). Với mỗi \(y\) mà \(f[\frac{x}{y}] = false\), ta lấy \(cnt[x] = min(cnt[\frac{x}{y}]) + 1\)

Về phần cài đặt, có hai hướng:

• QHĐ bottom-up: Ta đã có kết quả tại \(f[x]\), dùng giá trị này để cập nhật cho \(f[kx]\)
• Lưu \(p[x]\) là ước nguyên tố lớn/bé nhất của số \(x\) (bằng cách sàng) để phân tích \(x\) nhanh.

\(O(n \times log(n))\)

Subtask 4:

Để giải full, chỉ cần sử dụng ý tưởng ở subtask 3 nhưng cài đặt khéo hơn.

Nhận thấy số lượng ước số của một số \(\le 10^16\) vô cùng ít (\(< 30000\)). Ta có được một cách biểu diễn các trạng thái hợp lí hơn, như sau:

• Đầu tiên, phân tích \(n\) ra TSNT (\(O(\sqrt{n})\))
• Đệ quy để liệt kê mọi ước số của \(n\). Dùng thêm một map để ánh xạ/ nén các ước số này thành những số tự nhiên liên tiếp \(1,2,3,...\)
• Thực hiện QHĐ trên mảng có kích thước \(30000\)