Tóm tắt đề bài

Cho thẻ thông minh chứa \(m\) số \(k_1, k_2, \dots, k_m\) và mỗi phòng \(i\) chứa \(m\) số \(x_{i1}, x_{i2}, \dots, x_{im}\). Thẻ mở được phòng \(i\) khi:

Hãy tìm số lượng phòng mở được và liệt kê chỉ số các phòng đó (tăng dần).

Phân tích

• \(1 \le m, n \le 100\), mỗi số \(\le 10^{15}\).
• Tích trực tiếp có thể rất lớn (tràn kiểu số).
• Điều kiện “chia hết” giữa hai tích tương đương so sánh số mũ các thừa số nguyên tố trong phân tích.
• Với mỗi số \(a\), viết:

Khi đó:

Vì vậy, ta chỉ cần:

• Gom tổng số mũ từng prime của tích thẻ.
• Với mỗi phòng, gom tổng số mũ từng prime của tích phòng, rồi so sánh.

Lưu ý quan trọng: Code AC dùng phân tích thừa số nguyên tố kiểu thử chia \(i\) từ \(2\) đến \(\sqrt{x}\). Cách này phù hợp nếu dữ liệu thực tế/ẩn có các số không quá “khó” để factor (hoặc có cấu trúc đặc biệt). Về lý thuyết, với \(10^{15}\) thì đây không phải là cách tối ưu nhất, nhưng ta bám theo hướng của lời giải AC.

Hướng giải quyết

Nhận xét

• Không cần tính tích.
• Chỉ cần đếm tổng số mũ của từng prime.
• Nếu với mọi prime \(p\) xuất hiện trong phòng mà thẻ có số mũ không nhỏ hơn, thì phòng mở được.
  • Không cần duyệt các prime không xuất hiện trong phòng, vì yêu cầu chỉ là “thẻ đủ prime” để chia hết.

Thuật toán

1. Đọc \(m, n\).
2. Với \(m\) số trên thẻ:
   • Phân tích từng \(k_j\) ra prime \(\to\) map theso[p] += exponent.
3. Với từng phòng \(i\) từ \(1\) đến \(n\):
   1. Khởi tạo map ph rỗng.
   2. Đọc \(m\) số \(x_{ij}\):
      • Phân tích ra prime và cộng dồn vào ph.
   3. Kiểm tra:
      • Với mọi cặp \((p, cnt)\) trong ph, nếu theso[p] < cnt thì phòng không mở được.
   4. Nếu hợp lệ, lưu chỉ số \(i\) vào danh sách kết quả.
4. In số lượng phòng mở được và danh sách chỉ số.

Hàm phân tích thừa số (đúng như code AC)

• Duyệt \(i\) từ \(2\) đến khi \(i^2 > x\):
  • Trong khi \(x \bmod i = 0\):
    • tăng số mũ của \(i\), chia \(x\) cho \(i\).
• Nếu sau vòng lặp còn \(x > 1\) thì \(x\) là một prime lớn, số mũ \(1\).

Độ phức tạp

Gọi \(F(t)\) là thời gian phân tích một số \(t\) bằng thử chia đến \(\sqrt{t}\).

• Thời gian: xấp xỉ \(O\Big(\sum F(k_j) + \sum_{i=1}^{n}\sum_{j=1}^{m} F(x_{ij})\Big)\).
  • Với thử chia, \(F(t) = O(\sqrt{t})\) trong trường hợp xấu.
• Bộ nhớ: \(O(P)\) với \(P\) là số prime khác nhau xuất hiện trong dữ liệu (lưu trong map).

Code tham khảo

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// Phân tích thừa số nguyên tố bằng thử chia, trả về map prime -> số mũ
map<ll, int> factorize(ll x) {
    map<ll, int> res;
    for (ll i = 2; i * i <= x; ++i) {
        while (x % i == 0) {
            res[i]++;
            x /= i;
        }
    }
    if (x > 1) res[x]++; // phần còn lại là 1 prime
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    cin >> m >> n;

    // theso[p] = tổng số mũ của prime p trong tích k1*k2*...*km
    map<ll, int> theso;
    for (int i = 0; i < m; ++i) {
        ll kj;
        cin >> kj;
        auto f = factorize(kj);
        for (auto &p : f) theso[p.first] += p.second;
    }

    vector<int> res;
    for (int i = 1; i <= n; ++i) {
        // ph[p] = tổng số mũ của prime p trong tích của phòng i
        map<ll, int> ph;

        for (int j = 0; j < m; ++j) {
            ll x;
            cin >> x;
            auto f = factorize(x);
            for (auto &p : f) ph[p.first] += p.second;
        }

        bool ok = true;
        for (auto &p : ph) {
            ll prime = p.first;
            int need = p.second;
            if (theso[prime] < need) {
                ok = false;
                break;
            }
        }

        if (ok) res.push_back(i);
    }

    cout << res.size() << "\n";
    for (int idx : res) cout << idx << " ";
    cout << "\n";
    return 0;
}