Tóm tắt đề bài

Cho một dãy \(A\) gồm \(N\) số nguyên dương \(A_1, A_2, \dots, A_n\). Nhiệm vụ của bạn là tìm số nguyên dương \(D\) nhỏ nhất sao cho \(D > 1\) và tất cả các phần tử trong dãy \(A\) đều chia hết cho \(D\). Nếu không tìm được số \(D\) nào thỏa mãn, in ra \(-1\).

Phân tích

• Điều kiện: \(N \leq 10^5\), \(A_i \leq 10^6\).
• Nhận xét 1: Một số \(D\) là ước chung của cả dãy khi và chỉ khi \(D\) là ước của tất cả các số \(A_i\). Điều này tương đương với việc \(D\) là ước của \(\text{GCD}(A_1, A_2, \dots, A_n)\) (với \(\text{GCD}\) là ước chung lớn nhất).
• Nhận xét 2: Nếu \(G = \text{GCD}(A_1, A_2, \dots, A_n)\), thì mọi ước của \(G\) đều là ước chung của cả dãy. Để tìm ước chung nhỏ nhất lớn hơn \(1\), ta chỉ cần tìm ước nhỏ nhất lớn hơn \(1\) của \(G\).
• Nhận xét 3: Ước nhỏ nhất lớn hơn \(1\) của một số nguyên dương \(G > 1\) luôn luôn là một số nguyên tố.

Cách làm đơn giản (Brute Force)

Ý tưởng

Duyệt mọi số \(x\) từ \(2\) đến giá trị nhỏ nhất trong mảng \(A\). Với mỗi \(x\), kiểm tra xem tất cả các phần tử trong mảng có chia hết cho \(x\) hay không. Số \(x\) đầu tiên thỏa mãn chính là kết quả.

Độ phức tạp

• Thời gian: \(O(\min(A_i) \times N)\)
• Đánh giá: Với \(N = 10^5\) và \(A_i = 10^6\), độ phức tạp này lên tới \(10^{11}\), không thể vượt qua Subtask 2. Tuy nhiên, nó có thể ăn được điểm ở Subtask 1.

Code Brute Force

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int min_val = 1e6 + 7;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        min_val = min(min_val, a[i]);
    }

    int ans = -1;
    for (int x = 2; x <= min_val; x++) {
        bool ok = true;
        for (int i = 0; i < n; i++) {
            if (a[i] % x != 0) {
                ok = false;
                break;
            }
        }
        if (ok) {
            ans = x;
            break;
        }
    }
    cout << ans;
    return 0;
}

n = int(input())
a = list(map(int, input().split()))

min_val = min(a)
ans = -1
for x in range(2, min_val + 1):
    ok = True
    for val in a:
        if val % x != 0:
            ok = False
            break
    if ok:
        ans = x
        break
print(ans)

Hướng giải quyết (Tối ưu)

Thuật toán

1. Tính ước chung lớn nhất (GCD) của toàn bộ dãy số: \(G = \text{GCD}(A_1, A_2, \dots, A_n)\).
2. Nếu \(G = 1\), không tồn tại ước chung nào lớn hơn \(1\), in ra \(-1\).
3. Nếu \(G > 1\), ta cần tìm ước nhỏ nhất của \(G\) mà lớn hơn \(1\). Như đã nhận xét, số này chính là ước nguyên tố nhỏ nhất của \(G\).
4. Để tìm ước nguyên tố nhỏ nhất của \(G\), ta duyệt các số \(i\) từ \(2\) đến \(\sqrt{G}\):
   • Nếu \(G\) chia hết cho \(i\), thì \(i\) chính là ước nhỏ nhất cần tìm.
   • Nếu duyệt hết đến \(\sqrt{G}\) mà không tìm thấy \(i\) nào, thì chính \(G\) là một số nguyên tố, và kết quả là \(G\).

Ví dụ

Dãy \(A = \{12, 18, 24\}\)

• \(G = \text{GCD}(12, 18, 24) = 6\).
• Ước nhỏ nhất của \(6\) (khác \(1\)) là \(2\). Kết quả là \(2\).

Độ phức tạp

• Thời gian: \(O(N \log(\max A_i) + \sqrt{\max A_i})\). Trong đó \(O(N \log(\max A_i))\) là thời gian tính GCD của dãy và \(O(\sqrt{\max A_i})\) là thời gian tìm ước nhỏ nhất.
• Bộ nhớ: \(O(N)\) để lưu mảng hoặc \(O(1)\) nếu tính GCD trực tiếp khi nhập.

Code tham khảo

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

// Hàm tính GCD của hai số
int gcd(int a, int b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int g = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (i == 0) g = x;
        else g = gcd(g, x);
    }

    if (g <= 1) {
        cout << -1;
    } else {
        // Tìm ước nhỏ nhất khác 1 của g
        int ans = g;
        for (int i = 2; i * i <= g; i++) {
            if (g % i == 0) {
                ans = i;
                break;
            }
        }
        cout << ans;
    }

    return 0;
}

import math

def solve():
    try:
        line1 = input().split()
        if not line1: return
        n = int(line1[0])

        line2 = input().split()
        if not line2: return
        a = list(map(int, line2))
    except EOFError:
        return

    # Tính GCD của cả dãy
    g = a[0]
    for i in range(1, n):
        g = math.gcd(g, a[i])

    if g <= 1:
        print(-1)
    else:
        # Tìm ước nhỏ nhất khác 1 của g
        ans = g
        for i in range(2, int(math.sqrt(g)) + 1):
            if g % i == 0:
                ans = i
                break
        print(ans)

if __name__ == "__main__":
    solve()