Задача A. Баука и Гора Великих Чисел Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Баука любит прогуливаться по утрам, из-за этого с восходом солнца он пошел на гору Великих Чисел. С собой он взял любимый массив из N элементов, где i-е число равно ai. Баука хочет найти великое число для своего массива. Число x считается великим, если для него выполняется такое условие, что НОД(ai+x, aj+x) = 1 для всех 1 ≤ i < j ≤ N. Числа на горе представлены в виде Q запросов. В каждом запросе дается одно число. Помогите Бауке определить, будет ли данное число великим для его массива. Формат входных данных В первой строке находятся два целых числа N и Q (2 ≤ N ≤ 10^5, 1 ≤ Q ≤ 10^4) - количество чисел и запросов. Во второй строке находятся N целых чисел a1, a2, · · · , an (1 ≤ ai ≤ 10^5). В следующих Q строках дано по одному целому числу x (1 ≤ x ≤ 10^5). Формат выходных данных На каждый из Q запросов выведите «YES», если число является великим, иначе выведите «NO». Система оценки Подзадача 0: Примеры, 0 баллов Подзадача 1: N = 2, 20 баллов Подзадача 2: N, Q ≤ 100, 23 балла Подзадача 3: N, Q, ai, x ≤ 10^4, 27 баллов Подзадача 4: —, 30 баллов Пример стандартный ввод: 5 2 1 13 4 7 9 4 11 стандартный вывод: YES NO Замечание Рассмотрим первый запрос. После того как мы добавим 4 к каждому числу у нас получится массив: 5 17 8 11 13. Если мы возьмем НОД каждой пары из полученного массива, то он не превысит 1, значит ответ YES. Во втором запросе нужно добавить к изначальному массиву число 11. В полученном массиве первое число будет равно 12, второе 24. НОД(12, 24) = 12, отсюда следует что ответ NO.

Идея

Пусть после добавления запроса x получаются числа

[
b_i = a_i + x.
]

Нужно проверить, что никакой простой делитель не встречается хотя бы у двух чисел b_i.

Сразу обработаем важный случай: если в исходном массиве есть одинаковые a_i, то для любого x

[
\gcd(a_i+x, a_j+x)=a_i+x\ge 2,
]

поэтому ответ на все запросы — NO.

Далее считаем, что все a_i различны.

Малые простые числа

Все значения a_i + x не превосходят 200000. Поэтому если число составное, у него обязательно есть простой делитель не больше

[
\sqrt{200000} < 448.
]

Назовём простые числа p ≤ 447 малыми.

Для фиксированного малого простого p рассмотрим остатки a_i mod p.

Если два значения a_i и a_j имеют одинаковый остаток r, то при

[
x \equiv -r \pmod p
]

оба числа a_i+x и a_j+x делятся на p. Значит такой x сразу плохой.

Для каждого малого простого p заранее:

1. Находим остатки a_i mod p, которые встретились хотя бы дважды.

2. Помечаем все запросы x, для которых x ≡ -r mod p, как плохие.

3. Для каждого остатка сохраняем индекс единственного элемента с этим остатком, если он есть.

На это уходит около 86 · N, потому что простых чисел до 447 всего около 86.

Что остаётся проверить для хорошего по малым простым запроса

Пусть запрос x не был заранее помечен как плохой.

Тогда для каждого малого простого p среди всех чисел a_i+x делится на p не более одного числа.

Рассмотрим все элементы a_i+x, которые делятся хотя бы на один малый простой. Их не больше числа малых простых, то есть примерно 86.

Все остальные числа не имеют простых делителей не больше 447. Значит они не могут быть составными, иначе у них был бы малый делитель. Следовательно, остальные числа — различные простые числа.

Поэтому достаточно факторизовать только найденные “подозрительные” элементы.

Для каждого простого делителя p подозрительного числа проверяем:

• не встречался ли этот делитель у другого подозрительного числа;

• нет ли в массиве числа, равного самому p.

Вторая проверка нужна потому, что “неподозрительное” число может разделяться с составным числом только тогда, когда оно само равно этому простому делителю.

Корректность

Для малого простого p все плохие запросы отмечаются заранее: если два a_i имеют одинаковый остаток по модулю p, то при соответствующем x оба a_i+x делятся на p.

Если запрос прошёл предварительную проверку, то для каждого малого p существует не более одного числа a_i+x, кратного p.

Любое составное число среди a_i+x имеет простой делитель не больше 447, поэтому оно обязательно попадает в список подозрительных элементов.

Все непопавшие элементы не имеют малых делителей. Они не могут быть составными, значит это различные простые числа, а потому попарно взаимно просты.

Если НОД некоторой пары больше единицы, у неё есть общий простой делитель p.

• Если оба числа подозрительные, одинаковый делитель будет найден при факторизации.

• Если одно число не подозрительное, оно является простым и равно p; это обнаруживается проверкой наличия значения p среди a_i+x.

Таким образом, алгоритм выводит YES ровно для великих чисел.

Сложность

Пусть P — количество простых чисел не больше 447, P ≤ 86.

Предобработка:

[
O(N \cdot P + 10^5 \cdot P).
]

Один запрос:

[
O(P + P \log 200000).
]

Память:

[
O(N + 200000).
]

Код C++17

#include 
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector a(n);
    int maxA = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        maxA = max(maxA, a[i]);
    }
    vector queries(q);
    int maxX = 0;
    for (int i = 0; i < q; ++i) {
        cin >> queries[i];
        maxX = max(maxX, queries[i]);
    }
    vector present(maxA + 1, false);
    bool duplicate = false;
    for (int value : a) {
        if (present[value]) {
            duplicate = true;
        }
        present[value] = true;
    }
    if (duplicate) {
        for (int i = 0; i < q; ++i) {
            cout << "NO\n";
        }
        return 0;
    }
    int maxValue = maxA + maxX;
    // SPF — минимальный простой делитель.
    vector spf(maxValue + 1, 0);
    for (int i = 2; i <= maxValue; ++i) {
        if (spf[i] == 0) {
            spf[i] = i;
            if (1LL * i * i <= maxValue) {
                for (long long j = 1LL * i * i; j <= maxValue; j += i) {
                    if (spf[j] == 0) {
                        spf[j] = i;
                    }
                }
            }
        }
    }
    int root = 0;
    while (1LL * (root + 1) * (root + 1) <= maxValue) {
        ++root;
    }
    vector smallPrimes;
    for (int p = 2; p <= root; ++p) {
        if (spf[p] == p) {
            smallPrimes.push_back(p);
        }
    }
    vector bad(maxX + 1, false);
    // owner[k][r] — индекс единственного a_i с остатком r по модулю smallPrimes[k].
    vector> owner;
    owner.reserve(smallPrimes.size());
    for (int p : smallPrimes) {
        vector first(p, -1);
        vector multiple(p, false);
        for (int i = 0; i < n; ++i) {
            int r = a[i] % p;
            if (first[r] == -1) {
                first[r] = i;
            } else {
                multiple[r] = true;
            }
        }
        for (int r = 0; r < p; ++r) {
            if (!multiple[r]) {
                continue;
            }
            int start = (p - r) % p;
            if (start == 0) {
                start = p;
            }
            for (int x = start; x <= maxX; x += p) {
                bad[x] = true;
            }
        }
        owner.push_back(move(first));
    }
    vector usedIndex(n, 0);
    vector usedPrime(maxValue + 1, 0);
    int timer = 0;
    for (int x : queries) {
        if (bad[x]) {
            cout << "NO\n";
            continue;
        }
        ++timer;
        vector candidates;
        // Находим все a_i + x, имеющие малый простой делитель.
        for (int k = 0; k < (int)smallPrimes.size(); ++k) {
            int p = smallPrimes[k];
            int r = (p - x % p) % p;
            int id = owner[k][r];
            if (id != -1 && usedIndex[id] != timer) {
                usedIndex[id] = timer;
                candidates.push_back(id);
            }
        }
        bool ok = true;
        for (int id : candidates) {
            int value = a[id] + x;
            int current = value;
            while (current > 1) {
                int p = spf[current];
                // Такой простой делитель уже был у другого подозрительного числа.
                if (usedPrime[p] == timer) {
                    ok = false;
                    break;
                }
                usedPrime[p] = timer;
                // Проверяем, нет ли среди a_j + x числа, равного p.
                if (p != value) {
                    int neededA = p - x;
                    if (neededA >= 1 && neededA <= maxA &&
                        present[neededA]) {
                        ok = false;
                        break;
                    }
                }
                while (current % p == 0) {
                    current /= p;
                }
            }
            if (!ok) {
                break;
            }
        }
        cout << (ok ? "YES\n" : "NO\n");
    }
    return 0;
}