Editorial for Tập GCD

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Spoiler Alert

Hint 1

  • Ý tưởng ban đầu là tìm xem trong \(Set\) \(S\) có tồn tại cặp \(gcd(a, b) = k\) hay không (\(a\) có thể trùng \(b\))

Hint 2

  • Phân tích bài toán

Ta cần kiểm tra xem có tồn tại \((gcd(a, b) = k)\) <=> \((gcd(\frac{a}{k}, \frac{b}{k}) = 1)\) hay không

Vậy khi nhận các phần tử, ta loại các phần tử không phải bội của k

Ta sẽ xét các số \(d = gcd(a, b)\) vào \(set\) \(S\) tới khi không thể thêm vô nữa

Kiểm tra nếu tồn tại cặp thỏa mãn

Hint 3

  • Trong quá trình duyệt qua các cặp \((a, b) \in S\)

Gọi \(d = gcd(a, b)\)

Nếu \(d = 1\) thì ta tìm được cặp thỏa mãn -> return true

Nếu \(d = a\) thì \(\forall x \in N^* gcd(b, x) = 1 <=> gcd(k * a, x) = 1 <=> gcd(a, x) = 1\) nên ta sẽ loại bỏ \(a\) khỏi \(set\) \(S\)

Nếu \(d \neq a\) thì ta thêm phần tử \(d\) vào \(set\) \(S\)

  • Nếu kết thúc quá trình không tìm được cặp thỏa mãn -> return false

Reference AC code | \(O(?) \leq O(n^2 \times log_2(max\_val))\) time | \(O(n)\) auxiliary space | STL, GCD-problem, Branch_and_bound

C++
int query()
{
    /// Input
    int n = readInt();
    ll k = readLong();

    /// Tim cap (gcd(a, b) = k) <=> (gcd(a / k, b / k) = 1)
    set<ll> S;
    for (int i = 0; i < n; ++i) {
        ll x;
        cin >> x;
        if (x % k == 0) S.insert(x / k);
    }

    /// Neu $gcd(a, a) = 1$ => return true
    if (*S.begin() == 1) return puts("YES"), 0;

    /// Optimized
    while (true) {
        set<ll> T; /// tim cac cap ucln de them vao
        set<ll> M; /// loai bo cac uoc vo nghia
        for (ll a : S)
        {
            for (ll b : S)
            {
                int d = gcd(a, b);

                /// Neu gcd(a, b) = 1
                if (d == 1) return puts("YES"), 0;

                /// Neu gcd(a, b) = a thi voi moi (x > 1) ta co (gcd(x, a) = 1) <=> (gcd(x, b) = 1)
                if (d == a) M.insert(a);

                /// Neu gcd(a, b) # a thi minh them vao
                else T.insert(d);
            }
        }

        if (T.empty()) break; /// Neu khong the them duoc nua
        for (ll x : T) S.insert(x); /// Them uoc moi
        for (ll x : M) S.erase(x);  /// Xoa uoc vo nghia
    }

    return puts("NO"), 0; /// Neu khong ton tai cap (a, b) thoa man
}

Another Approach

Nếu ai hứng thú với con trỏ UwU

Reference AC code | \(O(?) \leq O(n^2 \times log_2(max\_val))\) time | \(O(n)\) auxiliary space | STL, GCD-problem, Branch_and_bound

C++
int query()
{
    /// input
    int n = readInt();
    ll k = readLong();

    /// Filter array: Only collect mutiple of k
    set<ll> S;
    for (int i = 0; i < n; ++i) {
        ll x;
        getUnsign(x); /// fast_input
        if (x % k == 0) S.insert(x / k); /// gcd(a, b) = k <=> gcd(a / k, b / k) = 1
    }

    /// gcd(a, a) = 1 case
    if (*S.begin() == 1) return puts("YES"), 0;

    for (int save = 0; save != S.size(); save = S.size()) { /// save return previous size of S
        for (set<ll>::iterator it1 = S.begin(); it1 != S.end(); ++it1) { /// *it1 = a
            for (set<ll>::iterator it2 = it1; it2 != S.end(); ++it2) {   /// *it2 = b
                int d = gcd(*it1, *it2);           /// d = gcd(a, b)
                if (d == 1) return puts("YES"), 0; /// gcd(a, b) = 1 case
                if (d == *it1) S.erase(*it1);      /// gcd(a, b) = a case
                else S.insert(*it1);               /// gcd(a, b) # a case
            }
        }
    }

    return puts("NO"), 0; /// cant found such pair
}

Another Approach

Cho ai thích Online Solving

Reference AC code | \(O(?) \leq O(n^2 \times log_2(max\_val))\) time | \(O(n)\) auxiliary space | Online Solving, STL, GCD-problem, Branch_and_bound

C++
void solve()
{
    /// input
    int n = readInt();
    ll k = readLong();

    set<ll> S;
    while (n--) {
        ll x;
        getUnsign(x); /// fast_input
        if (x % k != 0) continue; /// x is not mutiple of k 
        if (x == k) return puts("YES"), 0; /// gcd(a, a) = k case
        S.insert(x / k); /// gcd(a, b) = k <=> gcd(a / k, b / k) = 1
        for (set<ll>::iterator it1 = S.begin(); it1 != S.end(); ++it1) { /// *it1 = a
            for (set<ll>::iterator it2 = it1; (++it2 != S.end()); ) {    /// *it2 = b # a
                int d = gcd(*it1, *it2);           /// d = gcd(a, b)
                if (d == 1) return puts("YES"), 0; /// gcd(a, b) = 1 case
                if (d == *it1) S.erase(*it1);      /// gcd(a, b) = a case
                else S.insert(*it1);               /// gcd(a, b) # a case
            }
        }
    }

    return puts("NO"), 0; /// cant found such pair
}

Another Approach

Theo hướng của anh cuom1999

Reference AC code | \(O(n\) \times log_2(max_val))$ time | \(O(1)\) auxiliary space | GCD-problem, Online Solving

C++
int query() {
    ll n, k;
    cin >> n >> k;

    ll res = 0;
    for (int i = 0; i < n; ++i) {
        ll x;
        cin >> x;
        if (x % k == 0)
            res = gcd(res, x / k);
    }

    return cout << (res == 1 ? "YES\n" : "NO\n"), 0;
}

Comments

There are no comments at the moment.