Phân tích

Tìm số nguyên tiếp theo trong chuỗi có nghĩa là tìm ra các giá trị của \(A\), \(B\) và \(P\) phù hợp với các số đã cho và sử dụng chúng để tạo ra số tiếp theo.

Bài toán này có một vài trường hợp đặc biệt. Trong tất cả các trường hợp đó, điều quan trọng cần lưu ý là giá trị của \(P\) luôn phải lớn hơn mọi phần tử của chuỗi được tạo "ngẫu nhiên". (Số 8 không bao giờ có thể là số dư sau khi chia cho 7.) Ngoài ra, đề bài yêu cầu \(P\) không được lớn hơn \(10^D\). Hãy gọi tất cả các số nguyên tố thỏa mãn cả hai ràng buộc này là "số nguyên tố hợp lệ". Bây giờ, hãy xem xét các trường hợp đặc biệt.

K = 1

Trước hết, khi \(K\) bằng 1, câu trả lời luôn là "I don't know." Điều này là do chúng ta có thể chọn bất kỳ số nguyên tố hợp lệ \(P\) nào, đặt \(A = 0\) và \(B\) bằng 0 hoặc 1. Điều này sẽ cho chúng ta hai câu trả lời khác nhau.

K = 2 và hai phần tử của chuỗi giống nhau

Trong trường hợp này, câu trả lời là duy nhất vì phần tử tiếp theo của chuỗi chỉ phụ thuộc vào phần tử hiện tại. Nếu hai phần tử liên tiếp giống nhau, thì toàn bộ chuỗi sẽ bao gồm một số duy nhất lặp lại.

K > 2 và tất cả các phần tử của chuỗi giống nhau

Tương tự, phần tử tiếp theo phải giống với tất cả các phần tử khác.

K = 2 và hai phần tử của chuỗi khác nhau

Ở đây, câu trả lời luôn là "I don't know." Để thấy điều đó, hãy chọn bất kỳ số nguyên tố hợp lệ nào và xem xét các trường hợp \(A=0\) và \(A=1\). Nếu chúng ta gọi phần tử đầu tiên của chuỗi là \(x\) và phần tử thứ hai là \(y\), chúng ta có thể biểu diễn \(y\) dưới dạng hàm của \(x, A, B\) và \(P\): \(y = (A*x + B) \pmod P\). Trong cả hai trường hợp, chúng ta có thể giải phương trình này để tìm \(B\). Phần tử tiếp theo, \(z\), khi đó là \(z = (A*y + B) \pmod P\), và nó phải khác nhau trong hai trường hợp (\(A=0\) và \(A=1\)) miễn là \(x\) khác \(y\).

K = 3

Chúng ta sẽ duyệt trâu (brute force) tất cả các số nguyên tố hợp lệ và giải tìm \(A\) và \(B\). Sau đó, chúng ta sẽ sử dụng các giá trị này để tạo ra phần tử tiếp theo của chuỗi. Nếu tất cả các giá trị chúng ta nhận được theo cách này đều giống nhau, thì câu trả lời là duy nhất. Nếu chúng ta nhận được các câu trả lời hợp lệ khác nhau, thì câu trả lời là "I don't know."

Gọi 3 phần tử là \(x, y\) và \(z\). Bằng cách viết \(y\) dưới dạng hàm của \(x\) và \(z\) dưới dạng hàm của \(y\) rồi lấy \(z\) trừ \(y\), ta có:
\(z - y = (A*y + B) - (A*x + B) = A*(y - x) \pmod P\).

Chúng ta đã xử lý trường hợp \(x\) bằng \(y\), vì vậy có thể giả định rằng \(x\) và \(y\) khác nhau, do đó ta có thể chia cho hiệu của chúng. Điều này cho phép chúng ta giải tìm \(A\):
\(A = (z - y) * (y - x)^{-1} \pmod P\).

Việc tính nghịch đảo của \((y - x)\) có thể được thực hiện bằng thuật toán Euclid mở rộng, chạy trong thời gian \(O(\log P)\).

Khi đã có \(A\), việc giải tìm \(B\) rất dễ dàng:
\(B = (y - A*x) \pmod P\).

Câu trả lời khi đó là \((A*z + B) \pmod P\).

K > 3

Trong trường hợp này, chúng ta duyệt trâu \(P\), sử dụng 3 phần tử đầu tiên của chuỗi để giải tìm \(A\) và \(B\), và kiểm tra xem các phần tử còn lại có khớp với chuỗi được tạo bằng các tham số này hay không.

Dựa trên phân tích chính thức của Google Code Jam.