Hướng dẫn cho Nhóm số cùng số dư
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chuyển sang hiệu hai phần tử kề nhau
Đặt \(d_i=|a_{i+1}-a_i|\) với \(1\le i<n\). Các giá trị trong dãy khác nhau nên mọi \(d_i>0\).
Đoạn \([l,r]\) có ít nhất hai phần tử hợp lệ khi và chỉ khi:
Đoạn một phần tử luôn hợp lệ. Nhớ rằng đoạn \([l,r]\) trên dãy ban đầu tương ứng với \([l,r-1]\) trên dãy hiệu.
Chứng minh điều kiện GCD
Nếu mọi phần tử cùng dư khi chia cho \(m\), mỗi hiệu kề nhau chia hết cho \(m\), nên GCD của chúng ít nhất là \(m\ge2\).
Ngược lại, nếu GCD bằng \(g>1\), mọi hiệu kề nhau chia hết cho \(g\). Đi từ phần tử đầu sang phần tử cuối, ta thấy mọi phần tử cùng dư khi chia cho \(g\).
Sparse Table và hai con trỏ
Dựng Sparse Table truy vấn GCD trên dãy \(d\). Giữ đầu trái left, rồi duyệt đầu phải right từ \(1\) đến \(n-1\).
Khi GCD của \([\text{left},\text{right}]\) bằng \(1\), tăng left cho tới khi GCD lớn hơn \(1\) hoặc đoạn trở thành rỗng. Sau đó, độ dài hợp lệ trên dãy ban đầu là right - left + 2. Nếu dãy hiệu rỗng, công thức cho độ dài \(1\).
Chứng minh hai con trỏ
Khi thêm một hiệu vào bên phải, GCD chỉ có thể giữ nguyên hoặc trở thành một ước của giá trị trước. Một đoạn đã có GCD bằng \(1\) sẽ không trở nên hợp lệ khi nối thêm phần tử.
Vì vậy, những đầu trái đã bị bỏ ở bước trước vẫn không dùng được. Trong bước hiện tại, ta chỉ bỏ một đầu trái khi chính đoạn đang xét có GCD bằng \(1\). Khi dừng, đầu trái còn lại là nhỏ nhất có thể, nên cho đoạn dài nhất kết thúc tại right.
Độ phức tạp và kiểu số
Dựng bảng thực hiện \(O(n\log n)\) phép GCD và dùng \(O(n\log n)\) bộ nhớ. Mỗi con trỏ đi qua dãy một lần, nên phần quét thực hiện \(O(n)\) truy vấn GCD. Chi phí của một phép GCD còn phụ thuộc vào độ lớn của hai số.
C++ dùng long long: mỗi \(a_i\) không quá \(10^{18}\) và hiệu tuyệt đối vẫn nằm trong phạm vi này. Hai lời giải tham khảo dùng cùng cách; Python giữ mỗi hàng chỉ tới các đoạn còn hợp lệ.
Bình luận