Tóm tắt đề bài

Cho dãy số \(A\) gồm \(N\) phần tử nguyên dương. Tìm số nguyên dương \(P\) nhỏ nhất sao cho:

1. \(P\) là số chính phương.
2. \(P\) chia hết cho tất cả các phần tử \(a_i\) trong dãy \(A\).

In ra kết quả \(P \pmod{10^9+7}\).

Phân tích

• Điều kiện chia hết: Để \(P\) chia hết cho tất cả các \(a_i\), \(P\) phải là bội chung của tất cả các \(a_i\). Số \(P\) nhỏ nhất thỏa mãn điều kiện này chính là Bội chung nhỏ nhất (BCNN) của dãy số \(A\).
• Điều kiện số chính phương: Một số nguyên dương là số chính phương khi và chỉ khi trong dạng phân tích thừa số nguyên tố của nó, tất cả các số mũ của các thừa số nguyên tố đều là số chẵn.
• Kết hợp hai điều kiện:
  • Giả sử \(L = \text{BCNN}(a_1, a_2, \dots, a_n)\). Phân tích \(L\) ra thừa số nguyên tố: \(L = p_1^{e_1} \cdot p_2^{e_2} \dots p_k^{e_k}\).
  • Để \(P\) nhỏ nhất, \(P\) phải chia hết cho \(L\) và có các số mũ chẵn.
  • Với mỗi thừa số nguyên tố \(p_i\), số mũ của nó trong \(P\) phải là số chẵn nhỏ nhất mà lớn hơn hoặc bằng \(e_i\).
  • Do đó, nếu \(e_i\) chẵn, ta giữ nguyên \(e_i\). Nếu \(e_i\) lẻ, ta phải tăng lên thành \(e_i + 1\).

Hướng giải quyết

Thuật toán

1. Tìm số mũ lớn nhất của từng thừa số nguyên tố:

   • Duyệt qua từng số \(a_i\) trong dãy.
   • Phân tích \(a_i\) ra thừa số nguyên tố: \(a_i = p_1^{r_1} \cdot p_2^{r_2} \dots\).
   • Với mỗi số nguyên tố \(p\), ta duy trì \(f[p]\) là số mũ lớn nhất của \(p\) xuất hiện trong các phân tích của các \(a_i\). Giá trị \(f[p]\) chính là số mũ của \(p\) trong \(\text{BCNN}(A)\).

2. Xử lý số chính phương:

   • Sau khi duyệt hết dãy, với mỗi số nguyên tố \(p\) có số mũ \(f[p]\), nếu \(f[p]\) là số lẻ, ta tăng \(f[p]\) lên \(1\) để đảm bảo \(P\) là số chính phương.

3. Tính kết quả:

   • Kết quả \(P = \prod p^{f[p]} \pmod{10^9+7}\).

Kỹ thuật cài đặt

• Với \(a_i \le 10^7\), việc phân tích thừa số nguyên tố bằng cách chia thử thông thường sẽ chậm. Ta sử dụng Sàng Eratosthenes biến đổi để tìm ước nguyên tố nhỏ nhất (min_prime) của mọi số từ \(1\) đến \(10^7\).
• snt[i] lưu ước nguyên tố nhỏ nhất của \(i\). Khi đó, phân tích \(x\) sẽ mất \(O(\log x)\).
• Sử dụng mảng để lưu \(f[p]\) thay vì std::map để đạt tốc độ tối đa cho Subtask 3.

Độ phức tạp

• Thời gian: \(O(M \log \log M + N \log M)\), trong đó \(M = \max(a_i)\).
  • Sàng Eratosthenes: \(O(M \log \log M)\).
  • Phân tích \(N\) số: \(O(N \log M)\).
• Bộ nhớ: \(O(M)\) để lưu mảng sàng và mảng tần suất.

Code tham khảo

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

const int MOD = 1000000007;
const int MAXA = 10000005;

int n;
int snt[MAXA]; // Lưu ước nguyên tố nhỏ nhất của mỗi số
int max_exp[MAXA]; // Lưu số mũ lớn nhất của mỗi số nguyên tố

void sieve(int limit) {
    for (int i = 1; i <= limit; i++) snt[i] = i;
    for (int i = 2; i * i <= limit; i++) {
        if (snt[i] == i) {
            for (int j = i * i; j <= limit; j += i) {
                if (snt[j] == j) snt[j] = i;
            }
        }
    }
}

int main() {
    // Tối ưu nhập xuất
    ios::sync_with_stdio(false);
    cin.tie(0);

    if (!(cin >> n)) return 0;
    vector<int> a(n);
    int mx = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }

    // Sàng các số nguyên tố đến giá trị lớn nhất của a[i]
    sieve(mx);

    // Phân tích từng số a[i] để tìm số mũ lớn nhất của các thừa số nguyên tố
    for (int i = 0; i < n; i++) {
        int x = a[i];
        while (x > 1) {
            int p = snt[x];
            int count = 0;
            while (x % p == 0) {
                count++;
                x /= p;
            }
            if (count > max_exp[p]) {
                max_exp[p] = count;
            }
        }
    }

    long long res = 1;
    // Duyệt qua các số nguyên tố đã tìm được
    for (int p = 2; p <= mx; p++) {
        if (max_exp[p] > 0) {
            int e = max_exp[p];
            // Nếu số mũ lẻ, tăng lên 1 để thành số chính phương
            if (e % 2 != 0) e++;

            // Tính p^e % MOD
            for (int i = 0; i < e; i++) {
                res = (res * p) % MOD;
            }
        }
    }

    cout << res << endl;

    return 0;
}