0%

Problem 878


Problem 878


XOR-Equation B

We use $x\oplus y$ for the bitwise XOR of $x$ and $y$.

Define the XOR-product of $x$ and $y$, denoted by $x \otimes y$, similar to a long multiplication in base $2$, except that the intermediate results are XORed instead of the usual integer addition.

For example, $7 \otimes 3 = 9$, or in base $2$, $111_2 \otimes 11_2 = 1001_2$:
$$
\begin{aligned}
\phantom{\otimes 111} 111_2 \\
\otimes \phantom{1111} 11_2 \\
\hline
\phantom{\otimes 111} 111_2 \\
\oplus \phantom{11} 111_2 \phantom{9} \\
\hline
\phantom{\otimes 11} 1001_2 \\
\end{aligned}
$$
We consider the equation:
$$(a \otimes a) \oplus (2 \otimes a \otimes b) \oplus (b \otimes b) = k$$
For example, $(a, b) = (3, 6)$ is a solution to this equation for $k=5$.

Let $G(N,m)$ be the number of solutions to those equations with $k \le m$ and $0 \le a \le b \le N$.

You are given $G(1000,100)=398$.

Find $G(10^{17},1\ 000\ 000).$


异或等式(二)

用$x\oplus y$表示$x$和$y$按位异或的结果。

考虑$x$和$y$的$2$进制长乘法,但将中间结果的相加替换为按位异或,定义其结果为$x$和$y$的异或积,并记作$x \otimes y$。

例如,$7 \otimes 3 = 9$,或在$2$进制下,$111_2 \otimes 11_2 = 1001_2$:
$$
\begin{aligned}
\phantom{\otimes 111} 111_2 \\
\otimes \phantom{1111} 11_2 \\
\hline
\phantom{\otimes 111} 111_2 \\
\oplus \phantom{11} 111_2 \phantom{9} \\
\hline
\phantom{\otimes 11} 1001_2 \\
\end{aligned}
$$
考虑等式:
$$(a \otimes a) \oplus (2 \otimes a \otimes b) \oplus (b \otimes b) = k$$
例如,$(a, b) = (3, 6)$是上式取$k=5$时的一个解。

若上式取遍所有$k \le m$,考虑其所有满足$0 \le a \le b \le N$的解,记$G(N,m)$为所有这些解的数目。

已知$G(1000,100)=398$。

求$G(10^{17},1\ 000\ 000)$。