Dotcpp  >  编程题库  >  蓝桥杯2021年第十二届国赛真题-异或三角
题目 2616:

蓝桥杯2021年第十二届国赛真题-异或三角

时间限制: 2s 内存限制: 192MB 提交: 518 解决: 77

题目描述

给定 T 个数 n1, n2, · · · , nT,对每个 ni 请求出有多少组 a, b, c 满足:
1. 1 ≤ a, b, c ≤ ni;
2. a ⊕ b ⊕ c = 0,其中 ⊕ 表示二进制按位异或;
3. 长度为 a, b, c 的三条边能组成一个三角形。

输入格式

输入的第一行包含一个整数 T。
接下来 T 行每行一个整数,分别表示 n1, n2, · · · , nT。

输出格式

输出 T 行,每行包含一个整数,表示对应的答案。

样例输入

2
6
114514

样例输出

6
11223848130

提示

【评测用例规模与约定】
对于 10% 的评测用例,T = 1, 1 ≤ ni ≤ 200;
对于 20% 的评测用例,T = 1, 1 ≤ ni ≤ 2000;
对于 50% 的评测用例,T = 1, 1 ≤ ni ≤ 220
对于 60% 的评测用例,1 ≤ T ≤ 100000, 1 ≤ ni ≤ 220
对于所有评测用例,1 ≤ T ≤ 100000, 1 ≤ ni ≤ 230
标签