let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

VOI 2015 CRYPTKEY - Chìa khóa mã số

solution.md

Đây là một bài toán học, vì thể đòi hỏi khá nhiều sự phân tích. Dưới đây chúng ta sẽ nói thuật giải cho toàn bộ bài toán. Giả sử A và B là 2 số có dạng:

\[A = x_1^{a_1} \times x_2^{a_2} \times ... \times x_k^{a_k} \\ B = x_1^{b_1} \times x_2^{b_2} \times ... \times x_k^{b_k}\]

Với \(x_i\) là các thừa số nguyên tố và \(a_i, b_i \geq 0\).

Khi đó ước chung lớn nhất của A và B là:

\[UCLN(A, B) = x_1^{min(a_1, b_1)} \times x_2^{min(a_2, b_2)} \times ... \times x_k^{min(a_k, b_k)}\]

Trong khi đó bội chung nhỏ nhất của A và B là:

\[BCNN(A, B) = x_1^{max(a_1, b_1)} \times x_2^{max(a_2, b_2)} \times ... \times x_k^{max(a_k, b_k)}\]

Do giới hạn của bài toán rất lớn, ta không thể sinh tất cả các số có thể sinh ra được, thay vì đó ta sẽ tìm cách xây dựng K bằng cách xây dựng từng thừa số nguyên tố của K. Do đó công việc đầu tiên của ta là phân tích K ra dưới dạng thừa số nguyên. Việc phân tích K ra tích các thừa số nguyên có độ phức tạp là: \(O(\sqrt{K}) = O(10^6)\).

Giả sử K có dạng:

\[K = x_1^{c_1} \times x_2^{c_2} \times ... \times x_k^{c_k}\]

Xây dựng từng thừa số của K nghĩa là với từng giá trị \(x_i^{c_i}\) ta phải dùng các phép toán UCLN và BCNN để tạo ra một giá trị \(Y_i\) nào đó, mà Y phải chứa \(x_i^{c_i}\). Do ta chỉ cần thừa số \(x_i^{c_i}\) nên phần còn của \(Y_i\) càng tối thiểu càng tốt, nghĩa là \(Y_i\) là số nhỏ nhất trong tập S mà có chứa thừa số \(x_i^{c_i}\). Nhận thấy rằng phép UCLN cho ra giá trị nhỏ hơn 2 giá trị ban đầu, vì vậy tại bước này ta sẽ chỉ dùng hàm UCLN. Để tạo được \(Y_i\), ta lấy UCLN của tất cả các giá trị \(a_i\) thỏa mãn \(a_i\) chia hết cho \(x_i^{c_i}\) (để đảm bảo rằng giá trị thu được vẫn chứa \(x_i^{c_i}\)).

Giả sử ta có thể tìm được tất cả các giá trị \(Y_i\) (\(1 \leq i \leq k\)), ta có thể xây dựng K bằng cách lấy K’ là BCNN của tất cả k giá trị này. Tuy nhiên, để đảm bảo K’ = K (ta chỉ có thể đảm bảo rằng K là ước của K’), K phải là bội số của tất cả các \(Y_i\) (\(1 \leq i \leq k\)).

Độ phức tạp: \(O(\sqrt{K} + n\log^2(10^{12}))\) cho mỗi test.

Nguồn: Tạp chí tin học và nhà trường.

main.cpp
Open in Github • Download 
#include <cstdio>
#include <vector>
using namespace std;
#define LL long long

vector<LL> prime_factor(LL x) {
    vector<LL> res;
    LL d = 2;
    while (d*d <= x) {
        if (x % d == 0) {
            LL tmp = 1;
            while(x % d == 0) x /= d, tmp *= d;
            res.push_back(tmp);
        }
        d++;
    }
    if (res.empty() || x > 1) res.push_back(x);
    return res;
}

LL gcd(LL a, LL b) {
    LL r;
    while (b != 0) r=a%b, a=b, b=r;
    return a;
}

void test(const vector<LL> &a, LL k) {
    vector<LL> p = prime_factor(k);

    vector<LL> b(p.size(), 0);
    for (LL a: a) {
        for (int i=0; i<(int)b.size(); i++) {
            if (a % p[i] == 0) b[i] = gcd(a, b[i]);
        }
    }

    bool ok = true;
    for (LL b: b) ok &= (b > 0 && k % b == 0);

    printf("%s\n", ok? "YES":"NO");
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        vector<LL> a(n);
        for (LL &a: a) scanf("%lld", &a);
        LL k; scanf("%lld", &k);
        test(a, k);
    }
    return 0;
}
Comments