Nén Mảng GCD

Hướng tiếp cận

Tận dụng tính chẵn lẻ. Đếm số phần tử lẻ ($O$) và chẵn ($E$). Vì $O+E=2n$ (chẵn), $O$ và $E$ cùng tính chẵn lẻ.

• $O$ chẵn: ghép từng cặp lẻ-lẻ và chẵn-chẵn ⇒ tổng đều chẵn ⇒ $gcd\ge 2$.
• $O$ lẻ: bỏ $1$ phần tử lẻ và $1$ phần tử chẵn, sau đó áp dụng như trên.

Nhận xét quan trọng

1. Hai số cùng tính chẵn lẻ cộng lại cho số chẵn.
2. Nếu mọi tổng đều chẵn ⇒ $gcd\ge 2>1$.

Thuật toán

Tách chỉ số theo chẵn lẻ.
Nếu len(odd) lẻ: bỏ 1 odd và 1 even.
Ghép odd[i] với odd[i+1].
Ghép even[i] với even[i+1].

Độ phức tạp

• Thời gian: $O(n)$.
• Bộ nhớ: $O(n)$.