Tóm tắt đề bài

Cho một dãy số nguyên dương \(a\) gồm \(n\) phần tử. Yêu cầu tìm số có dạng \(2^k\) (\(k \ge 0\)) lớn nhất sao cho tồn tại ít nhất một phần tử \(a_i\) trong dãy chia hết cho \(2^k\).

Phân tích

• Điều kiện chia hết: Một số \(a_i\) chia hết cho \(2^k\) nghĩa là trong phân tích thừa số nguyên tố của \(a_i\), số mũ của thừa số 2 ít nhất phải là \(k\).
• Mục tiêu: Tìm giá trị \(2^k\) lớn nhất có thể. Điều này tương đương với việc tìm số \(a_i\) có chứa lũy thừa của 2 lớn nhất trong phân tích thừa số nguyên tố của nó.
• Giới hạn:
  • \(n \le 2 \cdot 10^6\): Số lượng phần tử khá lớn, cần một thuật toán tối ưu về thời gian, lý tưởng là \(O(n)\) hoặc \(O(n \log(\max a_i))\).
  • \(a_i \le 10^{18}\): Giá trị các phần tử có thể rất lớn, vượt quá phạm vi của kiểu dữ liệu int 32-bit, do đó cần dùng long long trong C++.

Hướng giải quyết

Nhận xét

Với mỗi số \(a_i\), ta cần tìm giá trị \(2^k\) lớn nhất mà \(a_i \vdots 2^k\). Giá trị này chính là "bit thấp nhất" (lowest set bit) của \(a_i\) nếu xét dưới dạng nhị phân. Ví dụ:

• \(a_i = 12\) (nhị phân: \(1100_2\)), các ước là lũy thừa của 2 là \(2^0=1, 2^1=2, 2^2=4\). Số lớn nhất là \(4\).
• \(a_i = 20\) (nhị phân: \(10100_2\)), số lớn nhất là \(4\).

Thuật toán

1. Khởi tạo một biến res = 1 để lưu kết quả lớn nhất tìm được (vì \(2^0 = 1\) luôn là ước của mọi số nguyên dương).
2. Duyệt qua từng số \(a_i\) trong dãy:
   • Tìm lũy thừa của 2 lớn nhất mà \(a_i\) chia hết. Ta có thể dùng vòng lặp: chừng nào \(a_i\) còn chia hết cho \(2 \cdot tmp\) thì nhân đôi \(tmp\).
   • Cập nhật res = max(res, tmp).
3. Ngoài ra, có một cách tối ưu hơn để lấy lũy thừa của 2 lớn nhất là ước của \(a_i\) bằng toán tử bit: tmp = ai & (-ai). Tuy nhiên, cách dùng vòng lặp như code mẫu vẫn đủ nhanh vì số lần lặp tối đa chỉ khoảng 60 lần (do \(2^{60} > 10^{18}\)).

Độ phức tạp

• Thời gian: \(O(n \cdot \log(\max a_i))\). Với \(n = 2 \cdot 10^6\) và \(\log(\max a_i) \approx 60\), tổng số phép tính khoảng \(1.2 \cdot 10^8\), có thể chạy kịp trong giới hạn thời gian thông thường (1-2 giây) nếu dùng ios_base::sync_with_stdio(false).
• Bộ nhớ: \(O(1)\) nếu đọc dữ liệu đến đâu xử lý đến đó, hoặc \(O(n)\) nếu lưu cả mảng.

Code tham khảo

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    // Tối ưu tốc độ nhập xuất
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    long long res = 1;
    for (int i = 0; i < n; ++i) {
        long long ai;
        cin >> ai;

        // Tìm lũy thừa của 2 lớn nhất là ước của ai
        // Cách 1: Dùng vòng lặp như code mẫu
        long long tmp = 1;
        while (ai % (2 * tmp) == 0) {
            tmp *= 2;
        }

        /* 
        Cách 2: Dùng toán tử bit (Nhanh hơn)
        long long tmp = ai & (-ai); 
        */

        if (tmp > res) {
            res = tmp;
        }
    }

    cout << res << endl;

    return 0;
}

Giải thích thêm về ai & (-ai)

Trong biểu diễn số nhị phân bù 2, -ai được tính bằng cách đảo ngược tất cả các bit của ai rồi cộng thêm 1. Phép toán ai & (-ai) sẽ giữ lại duy nhất bit 1 ở vị trí thấp nhất và biến các bit khác thành 0. Kết quả thu được chính xác là lũy thừa của 2 lớn nhất mà ai chia hết. Đây là một kỹ thuật phổ biến trong các cấu trúc dữ liệu như Fenwick Tree (Binary Indexed Tree).