Cho một dãy số dương. Tôi muốn chia mảng thành 2 tập con khác nhau sao cho tổng gcd (ước chung lớn nhất) của chúng là tối đa.

Mảng ví dụ:{6,7,6,7}.

Trả lời: Hai tập hợp con cần có là:{6,6}Và{7,7}; (các) gcd tương ứng của chúng là 6 và 7, và tổng=6+7=13;Đây là tổng gcd tối đa có thể.

Gcd:{8,12} Gcd là {4}, vì 4 là số lớn nhất giữa 8 và 12.

Để ý:gcd(X)=X Nếu tập hợp con chỉ chứa một phần tử.

Cách tiếp cận của tôi: bằng vũ lực, tìm tất cả các chuỗi con có thể có của mảng và sau đó tìm tổng tối đa, nhưng điều này sẽ không hoạt động nếu kích thước đầu vào lớn hơn 30 số. Tôi đang tìm kiếm một cách hiệu quả hơn.

(Các) Phần bổ sung: Kích thước tối đa của bất kỳ số đầu vào nào là 10^9, giới hạn thời gian: -1 giây có vẻ phù hợp, kích thước đầu vào có thể lớn tới 10^5

câu trả lời hay nhất

Tôi nghĩ đây thực sự là một câu hỏi dễ.

Đầu tiên, hãy bỏ qua khả năng một giá trị xuất hiện nhiều lần. Rõ ràng, tốt hơn là giữ tất cả các bản sao của một giá trị trong cùng một bộ sưu tập, vì việc di chuyển một số chúng đi nơi khác sẽ chỉ gây tổn hại cho GCD(biên tập:, trừ khi chỉ có một giá trị khác nhau). Vì vậy, chúng tôi giả định rằng tất cả các yếu tố là khác nhau. Hơn nữa, gọi M là giá trị lớn nhất của bất kỳ phần tử nào.

Hãy nghĩ theo cách này: có một giải pháp đơn giản, đặt phần tử cao nhất ở một bên và tất cả phần còn lại ở phía bên kia. "Tất cả phần còn lại" - GCD có thể là 1 (tất nhiên có thể cao hơn), vì vậy giải pháp này mang lại cho bạn M+1.

GCD của bất kỳ tập hợp con đầu vào nào có nhiều phần tử riêng biệt không thể cao hơn M/2 (vì ước số đó phải được nhân với một ước số khác ít nhất là 2 để có giá trị ban đầu, không cao hơn M). Vì thếbiên tập: Giải pháp tối ưu không thể bao gồm hai bộ, mỗi bộ có nhiều phần tử riêng biệt. Nó phải là một phần tử với tất cả các phần tử khác.

cân nhắc ngay bây giờhaiPhần tử cao nhất có giá trị M và Md đối với một số d. Nếu chúng ta không chọn bất kỳ trong số chúng làm đơn vị, thì tất cả chúng đều thuộc về nhóm lớn, điều đó có nghĩa là GCD của nhóm nhiều nhất là d (vì nếu g|M và g|Md thì g|d); người độc thân Phần đóng góp sẽ không vượt quá Md-1. Vì vậy, tổng số điểm tối đa là M-1 - nghĩa là nhỏ hơn số điểm chúng tôi sẽ nhận được nếu chọn giá trị cao nhất. Do đó, giá trị cao nhất hoặc giá trị cao thứ hai (khác) trong đầu vào phải nằm trong tập hợp riêng của nó.

Vì vậy, bạn phải làm như sau:

• Xử lý các trường hợp tầm thường trong đó chỉ có một giá trị riêng biệt.
• Ngược lại, lấy 2 phần tử cao nhất;
• Tính GCD g_0 của tất cả n-2 phần tử thấp nhất.
• Tính GCD cho g_with_highest = GCD(g_0, M) và g_with_second_highest = GCD(g_0, Md).
• Singleton được chọn bằng cách so sánh M + g_with_second_highest với (Md) + g_with_highest.

Tối đa hóa tổng GCD (ước số chung lớn nhất) của các phần chia đôi? , chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/56503879/