← 返回题目列表

AtCoder · abc384_f

I. 双和 2

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

分数: 500 点

问题陈述

对于正整数 x,定义 f(x) 如下:“虽然 x 是偶数,继续除以 2。最终值 这些划分之后的 x 是 f(x)。”例如, f(4)=f(2)=f(1)=1,和 f(12)=f(6)=f(3)=3.

给定一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N,查找 \displaystyle \sum_{i=1}^N \sum_{j=i}^N f(A_i+A_j).

约束

  • 1\le N\le 2\times 10^5
  • 1\le A_i\le 10^7
  • 所有输入值均为整数。

输入

输入由标准输入以以下格式给出:

N
A_1 A_2 \ldots A_N

输出

打印答案。


示例输入 1

2
4 8

示例输出 1

5

f(A_1+A_1)=f(8)=1, f(A_1+A_2)=f(12)=3, f(A_2+A_2)=f(16)=1。因此,打印 1+3+1=5.


示例输入 2

3
51 44 63

示例输出 2

384

示例输入 3

8
577752 258461 183221 889769 278633 577212 392309 326001

示例输出 3

20241214