Editorial for Ước chung sau dịch chuyển

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.

Gợi ý 1 - Các hiệu không đổi theo x

Khi cộng cùng một x vào mọi phần tử, hiệu giữa hai phần tử bất kỳ vẫn giữ nguyên. Ước chung của các số sau khi dịch phải chia hết cho ước chung lớn nhất của những hiệu đó.

Gợi ý 2 - Xét các ước có thể đạt được

Gọi g là gcd của các hiệu |a[i]-a[1]|. Với một ước d của g, cần chọn x sao cho a[1]+x chia hết cho d. Giá trị x nhỏ nhất không âm thỏa điều kiện là (d - a[1] mod d) mod d.

Lời giải đầy đủ

Quy về một số g cố định

Với mọi x, ta có gcd(a[1]+x, ..., a[N]+x) = gcd(a[1]+x, g), trong đó g = gcd(|a[i]-a[1]|) trên mọi i. Vì vậy, đáp án của một truy vấn luôn là một ước d của g.

Nếu g = 0 thì mọi phần tử bằng a[1]. Khi đó chọn x = K cho giá trị lớn nhất a[1]+K.

Điều kiện để một ước d dùng được

Để gcd đạt ít nhất d, cần d chia hết cho g và a[1]+x. Số x nhỏ nhất không âm thỏa điều kiện thứ hai là need[d] = (d - a[1] mod d) mod d. Ước d khả thi khi need[d] <= K.

Ta phân tích g một lần và liệt kê mọi ước. Sau đó sắp xếp các ước theo need[d], sắp xếp truy vấn theo K, rồi quét tăng dần để giữ ước lớn nhất đã khả thi.

Độ phức tạp

Phân tích g bằng thử ước mất O(sqrt(g)); gọi D là số ước của g, phần truy vấn mất O((D+Q) log(D+Q)).

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

struct Candidate {
    long long need;
    long long divisor;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<long long> a(n);
    for (long long& x : a) cin >> x;

    vector<long long> limit(q);
    for (long long& x : limit) cin >> x;

    long long g = 0;
    for (int i = 1; i < n; ++i)
        g = gcd(g, llabs(a[i] - a[0]));

    if (g == 0) {
        for (long long k : limit) cout << a[0] + k << endl;
        return 0;
    }

    vector<pair<long long, int>> factors;
    long long remaining = g;
    for (long long p = 2; p <= remaining / p; ++p) {
        if (remaining % p != 0) continue;
        int exponent = 0;
        do {
            remaining /= p;
            ++exponent;
        } while (remaining % p == 0);
        factors.push_back({p, exponent});
    }
    if (remaining > 1) factors.push_back({remaining, 1});

    vector<long long> divisors = {1};
    for (auto [prime, exponent] : factors) {
        int oldSize = (int)divisors.size();
        long long power = 1;
        for (int e = 1; e <= exponent; ++e) {
            power *= prime;
            for (int i = 0; i < oldSize; ++i)
                divisors.push_back(divisors[i] * power);
        }
    }

    vector<Candidate> candidates;
    for (long long d : divisors) {
        long long need = (d - a[0] % d) % d;
        candidates.push_back({need, d});
    }
    sort(candidates.begin(), candidates.end(), [](const Candidate& x, const Candidate& y) {
        return x.need < y.need;
    });

    vector<int> order(q);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
        return limit[i] < limit[j];
    });

    vector<long long> answer(q);
    long long best = 0;
    int pointer = 0;
    for (int id : order) {
        while (pointer < (int)candidates.size() && candidates[pointer].need <= limit[id]) {
            best = max(best, candidates[pointer].divisor);
            ++pointer;
        }
        answer[id] = best;
    }

    for (long long value : answer) cout << value << endl;
    return 0;
}

Loading...