/ 
Time Limit: 5 sec / Memory Limit: 1024 MiB
問題文
正整数 x に対して、 \rm{ord}_2(x) を 「 x が 2 で割り切れる回数」で定義します。
例えば \rm{ord}_2(24)=3, \rm{ord}_2(17)=0, \rm{ord}_2(32)=5 です。
長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
\displaystyle \sum^{N}_{ i=1 } \displaystyle \sum^{N}_{ j=i+1 } \rm{ord}_2(A_i + A_j) を求めてください。
制約
- 入力は全て整数
- 2 \le N \le 10^5
- 1 \le A_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
5 2 3 5 7 11
出力例 1
12
- \rm{ord}_2(2+3) = \rm{ord}_2(5) = 0
- \rm{ord}_2(2+5) = \rm{ord}_2(7) = 0
- \rm{ord}_2(2+7) = \rm{ord}_2(9) = 0
- \rm{ord}_2(2+11) = \rm{ord}_2(13) = 0
- \rm{ord}_2(3+5) = \rm{ord}_2(8) = 3
- \rm{ord}_2(3+7) = \rm{ord}_2(10) = 1
- \rm{ord}_2(3+11) = \rm{ord}_2(14) = 1
- \rm{ord}_2(5+7) = \rm{ord}_2(12) = 2
- \rm{ord}_2(5+11) = \rm{ord}_2(16) = 4
- \rm{ord}_2(7+11) = \rm{ord}_2(18) = 1
これらの合計は 12 です。
入力例 2
2 8 13
出力例 2
0
入力例 3
10 101736933 345226906 942125603 745512475 134406781 47730141 402464131 460079462 359290644 211134700
出力例 3
161
サンプルには含まれませんが、答えが 32 bit 符号付き整数型に収まらない場合があるので注意してください。
Problem Statement
For a positive integer x, let \rm{ord}_2(x) be the number of times 2 divides x.
For example, \rm{ord}_2(24)=3, \rm{ord}_2(17)=0, and \rm{ord}_2(32)=5.
You are given a length-N sequence of integers A=(A_1,A_2,\dots,A_N).
Find \displaystyle \sum^{N}_{ i=1 } \displaystyle \sum^{N}_{ j=i+1 } \rm{ord}_2(A_i + A_j).
Constraints
- All input values are integers.
- 2 \le N \le 10^5
- 1 \le A_i \le 10^9
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
5 2 3 5 7 11
Sample Output 1
12
- \rm{ord}_2(2+3) = \rm{ord}_2(5) = 0
- \rm{ord}_2(2+5) = \rm{ord}_2(7) = 0
- \rm{ord}_2(2+7) = \rm{ord}_2(9) = 0
- \rm{ord}_2(2+11) = \rm{ord}_2(13) = 0
- \rm{ord}_2(3+5) = \rm{ord}_2(8) = 3
- \rm{ord}_2(3+7) = \rm{ord}_2(10) = 1
- \rm{ord}_2(3+11) = \rm{ord}_2(14) = 1
- \rm{ord}_2(5+7) = \rm{ord}_2(12) = 2
- \rm{ord}_2(5+11) = \rm{ord}_2(16) = 4
- \rm{ord}_2(7+11) = \rm{ord}_2(18) = 1
Their sum is 12.
Sample Input 2
2 8 13
Sample Output 2
0
Sample Input 3
10 101736933 345226906 942125603 745512475 134406781 47730141 402464131 460079462 359290644 211134700
Sample Output 3
161
Note that the answer may not fit into 32-bit integer type, which is not exemplified in the samples.