Tìm dãy con dài nhất có BCNN tối đa K trong Python

Cho mảng A n phần tử khác nhau và số nguyên dương K. Tìm dãy con dài nhất có BCNN (Least Common Multiple) ≤ K. Trả về BCNN, độ dài và các chỉ số của dãy con.

Ví dụ: A = [3,4,5,6], K = 20 → BCNN=12, Length=3, Indexes=[0,1,3].

Giải thuật

Ý tưởng: với mỗi giá trị x ≤ K, đếm số phần tử của A chia hết cho x. Giá trị x có đếm lớn nhất là BCNN tìm được.

• Đếm tần suất các giá trị trong A (my_dict).
• Mảng count kích thước K+1, khởi tạo 0.
• Với mỗi key trong my_dict ≤ K: tăng count[key*i] += my_dict[key] cho mọi bội key*i ≤ K.
• Tìm i có count[i] lớn nhất → đó là BCNN, count[i] là độ dài.
• Liệt kê các chỉ số phần tử chia hết cho BCNN.

Ví dụ

from collections import defaultdict

def get_seq(A, k):
    n = len(A)
    my_dict = defaultdict(lambda: 0)
    for i in range(n):
        my_dict[A[i]] += 1
    count = [0] * (k + 1)
    for key in my_dict:
        if key <= k:
            i = 1
            while key * i <= k:
                count[key * i] += my_dict[key]
                i += 1
        else:
            break
    lcm = 0
    size = 0
    for i in range(1, k + 1):
        if count[i] > size:
            size = count[i]
            lcm = i
    if lcm == 0:
        print(-1)
    else:
        print(f"LCM = {lcm}, Length = {size}")
        print("Index values:", end=" ")
        for i in range(n):
            if lcm % A[i] == 0:
                print(i, end=" ")

k = 20
A = [3, 4, 5, 6]
get_seq(A, k)

Đầu vào

[3, 4, 5, 6], 20

Đầu ra

LCM = 12, Length = 3 Index values: 0 1 3