Counting pairs with product divisible by 6
Problem
Given a set of N natural numbers. It is necessary to determine the number of pairs of elements (ai, aj) of this set in which 1 <= i < j <= N and the product of the elements is a multiple of 6.
Write a time and memory efficient program to solve this problem.
Input
The first line of the input specifies the number of numbers N (\(1 < N <= 100000\)). Each of the following N lines contains one natural number not exceeding 1000.
Imprint
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
4
7
5
6
12
|
5 |
In the given set of 4 numbers, there are five pairs (7, 6), (5, 6), (7, 12), (5, 12), (6, 12), the product of whose elements is a multiple of 6.