题解：P10405 「SMOI-R1」Queue
ChampionCyan
·
·
题解
遇事不决先打表（bushi）
n=?| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ... |
ans| 1 | 0 | 3 | 0 | 5 | 4 | 3 | 0 | ... |
咦，0 怎么出现那么多？而且总是在 4 的倍数时出现！
那么我们就可以大胆猜测当 n \bmod 4 = 0 时答案一定为 0，现在开始证明了！
证明
题目解释，与和异或的意义
与，是一种两个数转换为二进制后的操作，对于每一位，只有两个数都为 1 时为 1，否则为 0。
异或，也是一种两个数转换为二进制后的操作，对于每一位，只有两个数有 0 为 0，否则为 1。
证明
解释中的 n 均满足 n\bmod 4=0\to ans=0（箭头的意思是那么）。
假设有 n\bmod 4=0\to ans=0（箭头的意思是那么）。
n+1 的答案
因为上一个人的编号是偶数且我们有一个公理：
任意一个数异或 0 都不变。
所以编号为 n+1 的人的答案一定为 n+1。
为什么任意一个数异或 0 都不变? 我们每一位拆开来看，若该二进制位上的数为 0，那么因为他和 0 该二进制位上的 0（0 的每一二进制位都是 0）相同，所以该二进制位还为 0，这一位相当于不变。若该二进制位上的数为 1，那么因为他和 0 该二进制位上的 0（0 的每一二进制位都是 0）不同，所以该二进制位还为 1，这一位也相当于不变。
于是我们得到 n\bmod 4=1\to ans=n（箭头的意思是那么）。
n+2 的答案
根据 n 的定义（见“证明”标题下内容），n + 1（即上一个人的答案，刚刚证明了）有一个特点，就是他的二进制位的后两位一定是 01，因为 n，一个可以被 4 整除的数的二进制位后两位为 0，反证法可以证明这点。
假设一个可以被 4 整除的数的二进制位后两位不为 0。这个数从二进制位的第三位以后所表示的数（ 4，8，16 …）都可以被 4 整除，所以该数除以 4 的余数一定为二进制后两位，而根据前面的假设，这个数的二进制位后两位不为 0，所以余数不为 0，与“可以被 4 整除的数”矛盾，因此一个可以被 4 整除的数的二进制位后两位一定为 0。
一个后两位为 0 的数（即 n）的数加一，后两位为 01（即 n+1）这个不难理解，后两位为 01 的数加一的数（即 n+2 ）后两位为 10 这个也不难理解。
这两个数进行与运算后的结果不难得出，因为两个数的后两位 01 和 10 与的结果为 0，前面的每一位都一样（因为几次加一都不影响前面几位），所以只用将 n+2 去掉后两位即可。
怎么去呢？很明显去掉后两位就是用 n+2 \bmod 4，根据定义，这个数为 2 ，因此 n+2 的答案为 (n + 2) - 2 = n。
于是我们得到 n\bmod 4=2\to ans=n-2（箭头的意思是那么）。
n+3 的答案
于是我们得到 $n\bmod 4=2\to ans=n-2$（箭头的意思是那么）
### $n+4$ 的答案
$n+4$ 的后两位为 $00$（能被 $4$ 整除的数后两位为 $00$，前面有证明），因此与 $ 3 $ 的后两位也是 $00$ 即 $0$，$3$ 前面的每一位都是 $0$，既然有 $0$，那么前面都为 $0$，前面后面都是 $0$，结果也是 $0$。
### 终极证明
我们已经证明若有 $n\bmod 4=0\to ans=0$，那么 $n + 4\bmod 4\to ans=0$，其实我们可以换一种表达，定义一个**正整数** $r$，那么根据前面的证明，$ans(4r)=0\to ans(4r+1))=0$，而通过打表可知 $r=1$ 时 $ ans(4r)=0$ 为真，因此 $r=1$ 时 $ ans(4(r+1))$ 为真，也就是 $r=2$ 时 $ans(4r)=0$ 为真；因为 $r=2$ 时 $ans(4r)=0$ 为真，所以 $r=2$ 时 $ans(4(r+1))$ 为真，也就是 $r=3$ 时 $ans(4r)=0$ 为真；因为 $r=2$ 时 $ans(4r)=0$ 为真，所以 $r=2$ 时 $ans(4(r+1))$ 为真，也就是 $r=3$ 时 $ans(4r)=0$ 为真...所以对于任意一个**正整数** $r$，都有 $ans(4r)=0$！
因为 $ans(4r)=0$，$r=2$ 时 $4r+1$ 的答案为 $n$ 可以由 $r=2$ 时的答案推出，$r=3$ 时 $4r+1$ 的答案为 $n$ 可以由 $r=3$ 时的答案推出，$r=4$ 时 $4r+1$ 的答案为 $n$ 可以由 $r=4$ 时的答案推出...无穷无尽，因此：
$n\bmod 4=1\to ans=n$。
因为 $ans(4r+1)=n$，$r=2$ 时 $4r+2$ 的答案为 $n-2$ 可以由 $r=2$ 时 $4r+1$ 的答案推出，$r=3$ 时 $4r+2$ 的答案为 $n - 2$ 可以由 $r=3$ 时 $4r+1$ 的答案推出，$r=4$ 时 $4r+2$ 的答案为 $n - 2$ 可以由 $r=4$ 时 $4r+1$ 的答案推出...无穷无尽，因此：
$n\bmod 4=2\to ans=n-2$。
因为 $ans(4r+2)=n-2$，$r=2$ 时 $4r+3$ 的答案为 $3$ 可以由 $r=2$ 时 $4r+2$ 的答案推出, $r=3$ 时 $4r+3$ 的答案为 $3$ 可以由 $r=3$ 时 $4r+2$ 的答案推出，$r=4$ 时 $4r+3$ 的答案为 $3$ 可以由 $r=4$ 时 $4r+2$ 的答案推出...无穷无尽，因此
$n\bmod 4=3\to ans=3$。
而且 $n=1,2,3$ 时（即特殊情况），打表也可得其满足前面的结论，所以特殊情况也不用特判。
证毕。
### 结论：
$n\bmod 4=0\to ans=0$。
$n\bmod 4=1\to ans=n$。
$n\bmod 4=2\to ans=n-2$。
$n\bmod 4=3\to ans=3$。
### code：
码应该很简单了，记得开 **long long**。
```c
#include <stdio.h>
long long solve() {
long long n;
scanf("%lld", &n);
switch (n % 4) {
case 1:
return n;
case 2:
return n - 2;
case 3:
return 3;
default:
return 0;
}
}
int main() {
int t;
scanf（"%d", &t）;
while（t--）
printf("%lld\n", solve());
return 0;
}
```