分数: 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