P7415 [USACO21FEB] Count the Cows G

As usual, Farmer John’s cows are scattered across his largest pasture. The pasture can be viewed as a huge 2D grid made of square cells (imagine a giant chessboard). The way the cows are placed on the pasture is quite fascinating. For every cell $(x, y)$ with $x \ge 0$ and $y \ge 0$, there is a cow at $(x, y)$ if, for all integers $k \ge 0$, the remainders of $\left\lfloor \frac{x}{3^k}\right\rfloor$ and $\left\lfloor \frac{y}{3^k}\right\rfloor$ when divided by $3$ always have the same parity. In other words, the two remainders are either both odd (both equal to $1$), or both even (equal to $0$ or $2$). For example, among the cells with $0 \le x, y < 9$, the cells containing cows are marked with 1 in the figure below. ``` x 012345678 0 101000101 1 010000010 2 101000101 3 000101000 y 4 000010000 5 000101000 6 101000101 7 010000010 8 101000101 ``` FJ is interested in the number of cows in a certain region of his pasture. He makes $Q$ queries, each given by three integers $x_i, y_i, d_i$. For each query, FJ wants to know how many cows lie on the diagonal cells from $(x_i, y_i)$ to $(x_i + d_i, y_i + d_i)$ (inclusive).

The first line contains $Q$ ($1 \le Q \le 10^4$), the number of queries. Each of the next $Q$ lines contains three integers $d_i$, $x_i$, and $y_i$ ($0 \le x_i, y_i, d_i \le 10^{18}$).

Output $Q$ lines, one line per query.

#### Constraints: - For an additional $8\%$ of the testdata, for each query $d_i \le 100$. - For an additional $32\%$ of the testdata, for each query $x + d = 3^{30} - 1$ and $y = 0$. - For an additional $52\%$ of the testdata, there are no additional constraints. Problem by: Benjamin Qi. Translated by ChatGPT 5