Question

Задача A. Баука и Гора Великих Чисел
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Баука любит прогуливаться по утрам, из-за этого с восходом солнца он пошел на гору Великих
Чисел. С собой он взял любимый массив из N элементов, где i-е число равно ai
. Баука хочет найти
великое число для своего массива.
Число x считается великим, если для него выполняется такое условие, что НОД(ai+x, aj +x) = 1
для всех 1 6 i < j 6 N.
Числа на горе представлены в виде Q запросов. В каждом запросе дается одно число. Помогите
Бауке определить, будет ли данное число великим для его массива.
Формат входных данных
В первой строке находятся два целых числа N и Q (2 6 N 6 105
, 1 6 Q 6 104
) - количество
чисел и запросов.
Во второй строке находятся N целых числа a1, a2, · · · , an (1 6 ai 6 105
).
В следующих Q строках дано по одному целому числу x (1 6 x 6 105
).
Формат выходных данных
На каждый из Q запросов выведите «YES», если число является великим, иначе выведите «NO».
Система оценки
Подзадача Дополнительные ограничения Баллы Необходимые подзадачи
0 Примеры 0 —
1 N = 2 20
2 N, Q 6 100 23 0
3 N, Q, ai
, x 6 104 27 0, 2
4 — 30 0, 1, 2, 3
Пример
стандартный ввод стандартный вывод
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.

Answer 1

Ответ:

Для решения данной задачи можно использовать алгоритм Эратосфена для нахождения всех простых чисел до заданного предела. Затем, для каждого запроса, можно проверить, является ли число великим, добавляя его к каждому элементу массива и находя НОД для каждой пары чисел. Если НОД равен 1 для всех пар, то число считается великим.

Вот пример кода на Python, который решает данную задачу:

```python

import math

def sieve_of_eratosthenes(limit):

primes = [True] * (limit + 1)

primes[0] = primes[1] = False

for i in range(2, int(math.sqrt(limit)) + 1):

if primes[i]:

for j in range(i * i, limit + 1, i):

primes[j] = False

return [i for i, is_prime in enumerate(primes) if is_prime]

def is_great_number(array, x):

for num in array:

if math.gcd(num + x, num) != 1:

return False

return True

# Чтение входных данных

N, Q = map(int, input().split())

array = list(map(int, input().split()))

# Находим все простые числа до максимального значения в массиве

primes = sieve_of_eratosthenes(max(array))

# Обрабатываем каждый запрос

for _ in range(Q):

x = int(input())

if is_great_number(array, x):

print("YES")

else:

print("NO")

```

В этом коде мы сначала определяем функцию `sieve_of_eratosthenes`, которая реализует алгоритм Эратосфена для нахождения всех простых чисел до заданного предела. Затем мы определяем функцию `is_great_number`, которая проверяет, является ли число великим для заданного массива. Мы проходимся по каждому числу в массиве и проверяем НОД для каждой пары чисел. Если НОД не равен 1 хотя бы для одной пары, то число не является великим.

Затем мы считываем входные данные, находим все простые числа до максимального значения в массиве с помощью функции `sieve_of_eratosthenes` и обрабатываем каждый запрос, вызывая функцию `is_great_number` и выводя результат на экран.