Kích thước dãy con lớn nhất mà mọi cặp đều là cặp "nice" trong Python

Cho dãy nums. Tìm kích thước lớn nhất của dãy con mà mọi cặp (p, q) trong đó là "cặp nice". Cặp nice thỏa mãn ít nhất một trong hai điều kiện:

1. Chẵn/lẻ của số ước nguyên tố phân biệt của p và q giống nhau.
2. Chẵn/lẻ của tổng tất cả ước dương của p và q giống nhau.

Giải thuật

• Với mỗi số trong nums, tính:
  • Số ước nguyên tố phân biệt (parity: chẵn/lẻ).
  • Tổng ước dương (parity: chẵn/lẻ).
• Xây dựng đồ thị: hai số có cạnh nếu cùng parity về ước nguyên tố hoặc cùng parity về tổng ước.
• Tìm clique lớn nhất (đồ thị nhỏ, dùng brute-force hoặc bitmask).
• Trả về kích thước clique lớn nhất.

Ví dụ mã Python

def solve(nums):
    n = len(nums)
    cnt = []  # parity of distinct prime divisors
    total = []  # parity of sum of divisors
    for i in nums:
        count = 0
        # find primes up to max(nums) for efficiency
        prime = []
        for j in range(2, max(nums)+1):
            if all(j % k for k in range(2, int(j**0.5)+1)):
                prime.append(j)
        for p in prime:
            if i % p == 0:
                count += 1
        cnt.append('even' if count % 2 == 0 else 'odd')
        tot = sum(d for d in range(1, i+1) if i % d == 0)
        total.append('even' if tot % 2 == 0 else 'odd')
    # build adjacency
    adj = [[False]*n for _ in range(n)]
    for i in range(n):
        for j in range(i+1, n):
            if cnt[i] == cnt[j] or total[i] == total[j]:
                adj[i][j] = adj[j][i] = True
    # brute-force max clique (n <= 15 typical)
    best = 0
    for mask in range(1, 1 << n):
        ok = True
        nodes = [i for i in range(n) if (mask >> i) & 1]
        for a in range(len(nodes)):
            for b in range(a+1, len(nodes)):
                if not adj[nodes[a]][nodes[b]]:
                    ok = False
                    break
            if not ok:
                break
        if ok:
            best = max(best, len(nodes))
    return best

nums = [2, 3, 6, 8]
print(solve(nums))  # Output: 3

Đầu vào

[2,3,6,8]

Đầu ra

3