A16513. Simons and Diophantus Equation
编程题
NOI/NOI+/CTSC
知识点
题目描述
我独自前行，走向远方，在渐渐消逝的光中静静等待着日落的最后一缕光。
—— SHUN，[CHAKA](https://open.spotify.com/track/1WL7sDRLAWmMGGJgQMUAGv)
Simons 给了你两个整数 $n$ 和 $m$。
请你计算有多少个有序三元组 $(i, j, k)$ 满足以下条件：
- $0\le i, j, k\le m$，并且
- 存在整数 $x$ 和 $y$，使得 $(i \oplus j) \cdot x + (j \oplus k) \cdot y = n$，其中 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。
—— SHUN，[CHAKA](https://open.spotify.com/track/1WL7sDRLAWmMGGJgQMUAGv)
Simons 给了你两个整数 $n$ 和 $m$。
请你计算有多少个有序三元组 $(i, j, k)$ 满足以下条件：
- $0\le i, j, k\le m$，并且
- 存在整数 $x$ 和 $y$，使得 $(i \oplus j) \cdot x + (j \oplus k) \cdot y = n$，其中 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。
输入格式
每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。
接下来每组测试用例包含一行，包含两个整数 $n$ 和 $m$（$1\le n\le 10^9$，$1\le m\le 3\cdot 10^5$）——给定的整数。
保证所有测试用例中 $m$ 的总和不超过 $3\cdot 10^5$。
接下来每组测试用例包含一行，包含两个整数 $n$ 和 $m$（$1\le n\le 10^9$，$1\le m\le 3\cdot 10^5$）——给定的整数。
保证所有测试用例中 $m$ 的总和不超过 $3\cdot 10^5$。
输出格式
对于每个测试用例，输出一个整数，表示满足条件的有序三元组 $(i,j,k)$ 的数量。
输入输出样例
输入 #1
5 3 2 4 6 1 1 7 20 720 2025
输出 #1
18 254 6 5558 7864357450
说明/提示
在第一个测试用例中，共有 $18$ 个满足条件的三元组。例如：
- $(2,1,2)$ 是一个合法的三元组，因为方程 $(2\oplus 1)\cdot x+(1\oplus 2)\cdot y=3$ 存在整数解 $x=3$，$y=-2$。
- $(1,1,0)$ 也是一个合法的三元组，因为方程 $(1\oplus 1)\cdot x+(1\oplus 0)\cdot y=3$ 存在整数解 $x=100$，$y=3$。
- $(2,0,2)$ 不是合法的三元组，因为方程 $(2\oplus 0)\cdot x+(0\oplus 2)\cdot y=3$ 没有整数解。
- $(1,1,1)$ 不是合法的三元组，因为方程 $(1\oplus 1)\cdot x+(1\oplus 1)\cdot y=3$ 没有整数解。
- $(3,2,1)$ 不是合法的三元组，因为 $3 > 2$。
- $(2,1,2)$ 是一个合法的三元组，因为方程 $(2\oplus 1)\cdot x+(1\oplus 2)\cdot y=3$ 存在整数解 $x=3$，$y=-2$。
- $(1,1,0)$ 也是一个合法的三元组，因为方程 $(1\oplus 1)\cdot x+(1\oplus 0)\cdot y=3$ 存在整数解 $x=100$，$y=3$。
- $(2,0,2)$ 不是合法的三元组，因为方程 $(2\oplus 0)\cdot x+(0\oplus 2)\cdot y=3$ 没有整数解。
- $(1,1,1)$ 不是合法的三元组，因为方程 $(1\oplus 1)\cdot x+(1\oplus 1)\cdot y=3$ 没有整数解。
- $(3,2,1)$ 不是合法的三元组，因为 $3 > 2$。