Count the Cows

题目描述

和往常一样，农夫约翰的奶牛分散在他最大的牧场上；牧场可以看作由正方形“格子单元”组成的巨大二维网格（可以想象成一张巨大的棋盘）。 牧场上奶牛的分布规律十分有趣。对于每个满足 $x\ge 0$ 且 $y\ge 0$ 的格子 $(x,y)$，当且仅当对所有整数 $k\ge 0$，将 $\left\lfloor \frac{x}{3^k}\right\rfloor$ 和 $\left\lfloor \frac{y}{3^k}\right\rfloor$ 分别除以 3 所得的余数具有相同的奇偶性时，$(x,y)$ 处存在一头奶牛。换句话说，这两个余数要么都为奇数（等于 $1$），要么都为偶数（等于 $0$ 或 $2$）。例如，下图中用 1 标出了所有满足 $0\le x,y<9$ 且含有奶牛的格子。 x 012345678

0 101000101 1 010000010 2 101000101 3 000101000 y 4 000010000 5 000101000 6 101000101 7 010000010 8 101000101 FJ 想知道牧场某些区域里有多少头奶牛。他提出 $Q$ 个询问，每个询问由三个整数 $x_i,y_i,d_i$ 组成。对于每个询问，FJ 想知道在从 $(x_i,y_i)$ 到 $(x_i+d_i,y_i+d_i)$ 的对角线范围内（包含端点）这些格子中一共有多少头奶牛。

输入格式

第一行包含 $Q$（$1\le Q\le 10^4$），表示询问数量。 接下来 $Q$ 行每行包含三个整数 $d_i$, $x_i$, 和 $y_i$（$0\le x_i,y_i,d_i\le 10^{18}$）。

输出格式

输出 $Q$ 行，每行对应一个询问的答案。

8
10 0 0
10 0 1
9 0 2
8 0 2
0 1 7
1 1 7
2 1 7
1000000000000000000 1000000000000000000 1000000000000000000

11
0
4
3
1
2
2
1000000000000000001

提示

SCORING: 测试点 2 满足对每个询问都有 $d_i\le 100$。 测试点 3-6 满足对每个询问都有 $x+d=3^{30}-1$ 且 $y=0$。 测试点 7-12 没有额外限制。 题目来源：Benjamin Qi

标签: USACO|2021|Gold

来源

USACO|2021|Gold