Hint 1: Chỉ cần quan tâm các số không có ước chính phương

Hint 2: \(\sqrt{500} = 22.3\)

Hint 3: Mỗi số từ \(1\) đến \(500\) chỉ chứa tối đa một ước nguyên tố lớn hơn \(22\).

Hint 4: Có \(8\) số nguyên tố nhỏ hơn \(22\).

Hint 5: Gọi \(p(n)\) là ước nguyên tố lớn hơn 22 của \(n\). Nếu hai số \(m, n\) có \(p(m) = p(n)\) thì ta chỉ có thể chọn tối đa một số.

Lời giải:

Đầu tiên, chia các số \(1, 2, ..., n\) vào các nhóm, số \(i\) thuộc nhóm \(p(i)\). Các số không có ước nguyên tố \(> 22\) thì xem mỗi số như một nhóm riêng.

Vì chỉ cần quan tâm các ước nguyên tố < 22, ta sẽ lưu trạng thái là 8 bit 0/1 cho 8 số nguyên tố < 22. Bit thứ \(i\) = 1 nếu số nguyên tố thứ \(i\) đã được chọn. \(dp[k][bit]\) cho ta biết số tập con có size = \(k\) và thỏa mãn điều kiện của \(bit\).

Với mỗi nhóm, chúng ta chọn ra tối đa một số. Vì vậy, chúng ta có thể for theo từng nhóm này. Giả sử trước một nhóm, chúng ta có mảng \(dp\_old[0..k][0..255]\). Chúng ta sẽ cập nhật như sau:

// không chọn số nào
for i = 0 to k:
  for bit = 0 to 255:
    dp[i][bit] = dp_old[i][bit]

// chọn 1 số trong nhóm
for i trong nhóm:
  tạo bitI là bit đại diện cho số i, bit thứ j = 1 nếu i chia hết số nguyên tố thứ j
  for bit = 0 to 255:
    if (bit | bitI) == 0:  // hai bit không giao nhau
      for j = 1 to k:
        dp[j][bit & bitI] += dp_old[j - 1][bitI]

Đáp số là tổng \(dp[0] + ... + dp[255]\).

Độ phức tạp: \(O(255 * nk)\)