Модуль: B27 (C4) - анализ пар


Задача

4 /23


Подсчет пар с произведением кратным 6

Задача

Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых \(1 <= i < j <= N \)и произведение элементов кратно 6. 

Напишите эффективную по времени и памяти программу для решения этой задачи. 

Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 <= N <= 100000\)). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.

Выходные данные
Ввыведите ответ на задачу

 

 

Примеры
Входные данные Выходные данные
1
4
7
5
6
12
5
В приведённом наборе из 4 чисел имеются пять пар (7, 6), (5, 6), (7, 12), (5, 12), (6, 12), произведение элементов которых кратно 6.