Tóm tắt đề bài

Cho dãy \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(n \le 1000\), \(a_i \le 10^{18}\)). Hãy tìm một tập con có nhiều phần tử nhất sao cho tồn tại một số \(d > 1\) mà mọi phần tử trong tập con đều chia hết cho \(d\). In ra số lượng phần tử lớn nhất đó.

Phân tích

Bài toán tương đương với:

• Tìm \(d > 1\) sao cho số lượng phần tử chia hết cho \(d\) là lớn nhất.
• Đáp án là:

Khó khăn:

• \(a_i\) rất lớn (tới \(10^{18}\)) nên không thể duyệt mọi ước số theo kiểu truyền thống.
• Nhưng \(n \le 1000\) nên có thể khai thác các phép \(\gcd\) giữa các cặp phần tử.

Nhận xét quan trọng:

• Nếu một tập con có ước chung \(d>1\), thì với bất kỳ hai phần tử trong tập con, \(\gcd(a_i, a_j)\) sẽ chia hết cho \(d\), và thường sẽ cho ta một ứng viên \(\gcd > 1\) để thử.
• Do đó, tập các \(\gcd\) của mọi cặp \((i,j)\) là nguồn ứng viên tự nhiên cho \(d\).

Hướng giải quyết

Ý tưởng chính của code AC

Code làm 2 phần để tìm các ứng viên \(d\):

1. **Thu thập các \(\gcd(a_i, a_j)\) với \(i<j\) và \(\gcd > 1\):
2. Duyệt tất cả cặp \((i, j)\), tính \(g=\gcd(a_i,a_j)\).
3. Nếu \(g>1\) thì đưa vào một set để loại trùng.

4. Với mỗi \(x\) trong set, đếm xem có bao nhiêu \(a_i\) chia hết cho \(x\), cập nhật đáp án.

5. Bổ sung kiểm tra một số lượng nhỏ các số nguyên tố nhỏ:

6. Code sàng nguyên tố tới \(10^6\) và chỉ thử khoảng 5555 số nguyên tố đầu tiên.
7. Với mỗi số nguyên tố \(p\), đếm số phần tử chia hết cho \(p\), cập nhật đáp án.

Phần (2) là một “lưới an toàn” trong trường hợp ước chung tối ưu là một nguyên tố nhỏ nhưng không xuất hiện trực tiếp dưới dạng một giá trị \(\gcd\) trong tập ứng viên (hoặc để tăng độ chắc chắn thực nghiệm).

Thuật toán chi tiết

1. Đọc \(n\) và mảng \(a[1..n]\).
2. Khởi tạo set<ll> s.
3. Với mọi \(1 \le i < j \le n\):
4. Tính \(g = \gcd(a_i, a_j)\).
5. Nếu \(g > 1\) thì s.insert(g).
6. Khởi tạo res = 1.
7. Với mỗi \(x\) trong s:
8. Đếm cnt = số lượng \(i\) sao cho \(a_i \bmod x = 0\).
9. res = max(res, cnt).
10. Sàng nguyên tố tới \(10^6\), lấy danh sách các số nguyên tố p.
11. Thử lần lượt các số nguyên tố đầu tiên (tối đa 5555 số):
12. Đếm cnt = số lượng \(i\) sao cho \(a_i \bmod prime = 0\).
13. res = max(res, cnt).
14. In res.

Trực giác đúng

• Nếu tồn tại tập con lớn nhất có ước chung \(d>1\), thì mọi phần tử trong tập con đều chia hết cho \(d\), do đó nhiều cặp trong số chúng sẽ có \(\gcd\) là một bội của \(d\) (ít nhất \(>1\)).
• Khi ta thử các giá trị \(\gcd\) thu được, việc đếm lại số phần tử chia hết cho chúng sẽ phát hiện được “cụm” chia hết chung lớn.
• Việc thử thêm các nguyên tố nhỏ giúp bắt các trường hợp mà ước chung tốt nhất là một nguyên tố nhỏ (phổ biến trong dữ liệu ngẫu nhiên).

Độ phức tạp

Gọi \(K\) là số lượng giá trị \(\gcd>1\) khác nhau trong set.

• Thời gian:
  • Tính \(\gcd\) mọi cặp: \(O(n^2 \log \max a)\).
  • Với mỗi ứng viên \(x\), đếm lại qua \(n\) phần tử: \(O(Kn)\).
  • Thử thêm ~5555 nguyên tố: \(O(5555 \cdot n)\).
• Bộ nhớ:
  • Lưu mảng \(a\): \(O(n)\).
  • Lưu set các gcd: \(O(K)\).
  • Mảng sàng tới \(10^6\): \(O(10^6)\).

Với \(n \le 1000\), cách làm này thường chạy tốt trong thực tế.