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