Hướng dẫn cho Tập GCD

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

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;
}

Bình luận

Không có bình luận nào.