Задачи
Делимость
Делимость
Имеется набор целых чисел a1
, a2
, ..., an
. Найти количество чисел от l до r включительно, которые делятся хотя бы на одно число из этого набора.
Входные данные:
Состоит из нескольких тестов. Первая строка каждого теста содержит два целых числа l (1 ≤ l ≤ 109
) и r (1 ≤ r ≤ 109
). Следующая строка содержит количество элементов n (1 ≤ n ≤ 18) в наборе и сам набор этих чисел. Каждое число в наборе принимает значение от 1 до 109
.
Выходные данные:
Для каждого теста в отдельной строке вывести количество чисел от l до r включительно, которые делятся хотя бы на одно из чисел из набора a1
, a2
, ..., an
.
Входные данные #1
293 784 1 1 579000 987654 2 1 2 1 1000000000 2 2 3
Выходные данные #1
492 408655 666666667