75. Подсчет пар с произведением кратным 6
Задача
Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых 1 ≤ i < j ≤ N и произведение элементов кратно 6. Напишите эффективную по времени и по памяти программу для решения этой задачи.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 100000). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.
В приведённом наборе из 4 чисел имеются пять пар (7, 6), (5, 6), (7, 12), (5, 12), (6, 12), произведение элементов которых кратно 6.
(c) Д.В. Богданов