2616 问题 D: 蓝桥杯2021年第十二届国赛真题-异或三角
时间限制: 1s
内存限制: 128MB 提交: 504 解决: 75
题目描述
给定 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 行，每行包含一个整数，表示对应的答案。
提示
【评测用例规模与约定】
对于 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。