Power of Two

0

0 votes
Problem

Rakesh has an array A having N positive integers. He wants to select indices i and j ( 1i<jN ) such that the maximum power of 2 that divides A[i]×A[j] is at max 1 . In how many ways can he do this ?

 

INPUT:

First line contains integer N, which denotes size of the array.

Second line contains N space separated integers, i.e the elements of A

 

CONSTRAINTS:

1N1051A[i]109

 

OUTPUT:

The required answer in one line.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The possible pairs of elements he can select are (3,2), (5,2) and (3,5) since the maximum power of 2 that divides 3x2=6 is 1, 5x2=10 is 1, and 3x5=15 is 0 .

Editor Image

?