Задача №112729. Экономический кризис
Экономический кризис вынуждает центробанки многих стран выделять большие пакеты экономической помощи инвестиционным и сберегательным банкам для поддержания ликвидности и сохранения кредитных рынков. Центробанк Флатландии планирует выделить N пакетов помощи. Каждый пакет характеризуется его суммой A i . Банки предоставили запросы на помощь. На данный момент поступило M запросов. Каждый запрос характеризуется его продолжительностью B i дней. Законы Флатландии требуют, чтобы при возвращении пакета помощи банк каждый день возвращал центробанку одинаковую целую сумму флатландских рублей. Таким образом, пакет с суммой A и продолжительностью B можно выделить только в случае если A делится на B . По известной информации о пакетах помощи и запросах подсчитайте количество возможных пар пакет-запрос.
Первая строка содержит целое число N — количество пакетов помощи (1 ≤ N ≤ 100.000) . Вторая строка содержит N целых чисел: a 1 , a 2 , ... , a N (1 ≤ a i ≤ 10 6 ) . Третья строка содержит целое число M — количество запросов (1 ≤ M ≤ 100.000) . Четвертая строка содержит M целых чисел: b 1 , b 2 , ... , b M (1 ≤ b i ≤ 10 6 ) .
Выведите количество возможных пар.
Пары могут быть следующие: (3, 1) дважды как ( a 1 , b 1 ) и ( a 1 , b 2 ) , (3, 3) , (4, 1) дважды, (4, 2) , (5, 1) дважды, (6, 1) дважды, (6, 2) и (6, 3) .
Тесты к этой задаче состоят из трех групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
4 3 4 5 6 4 1 1 2 3
12