← 返回题目列表

AtCoder · past18_k

K. 能被 2 整除的次数

中文机器翻译题面 查看原题

问题陈述

对于正整数 x,让 \rm{ord}_2(x) 是次数 2 划分 x.
例如, \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- 位整数类型,示例中未举例说明。