题解 P7827 【「RdOI R3 附加」ACP】
littleKtian
·
·
题解
upd on 2021.9.20：得到了一种新的加减法做法。
upd on 2021.8.19：对 4 和 6 的做法进行了小修改。
题目。
------------
### task 1
我估计大部分人上来看到交换第一时间想到的是这个：`int t=x;x=y,y=t;`
但这里没有直接对任意变量赋值的操作，所以这种想法没啥用。
实际上对于两个整数的交换我们还有另一种异或的做法：`x^=y,y^=x,x^=y;`
手玩一下很容易证明这是对的，所以利用异或操作就能做到 $5$ 步内了。
### task 2
我们先考虑如何计算 $a+b$。
令 $a'=a \operatorname{xor} b,b'=(a \operatorname{and} b)\times 2$，可以发现 $a+b=a'+b'$。
不断重复上面的操作，可以发现每次 $b$ 在 $2$ 进制下的最低位一定是在不断升高的，所以最多重复 $64$ 次 $b$ 就会变成 $0$，此时 $a$ 就是结果。
考虑 $a-b$。一种方法是先对 $b$ 取反得到 $b'$ 然后计算 $a+b'+1$（利用取反和右移操作可以得到 $1$）。另一种是先对 $a$ 取反得到 $a'$，计算 $a'+b$ 后再次取反即可得到 $a-b$。因为这个数据点的操作次数并没有卡的很死所以两者均可。
~~场上脑抽了以为不能直接得到 $1$ 所以写的第二种。~~
实际上减法还有一种直接做的做法（而且比加法还要短很多）：
考虑到二进制下的异或不仅在一定情况下和加法类似 $(0\operatorname{xor}1=0+1=1)$，也在某些情况下和减法类似 $(1\operatorname{xor}1=1-1=0)$，所以依然考虑从异或入手。
记 $c=a \operatorname{xor} b,x=a \operatorname{and} c,y=b \operatorname{and} c$，显然有 $a-b=x-y$ 和 $c=x+y$。
于是 $a-b=(x+y)-y\times2=c-y\times 2$，由上面同理可发现最多重复 $64$ 次操作就能使 $b$ 变为 $0$。
这个做法比上面最好的一点就是不需要再留空间存贮某些中间值，可以直接覆盖掉，所以会少掉很多中间移动变量的操作（实际上这个做法单次只需要 $3$ 步）。
当然也可以结合上面提到的取反的思想反过来实现加法。
### task 3
快读有一个比较经典的写法：`x=(x<<1)+(x<<3)+(ch^48)`，我们可以直接利用左移、异或以及之前的加法操作求出结果。
注意到每一步后的答案范围远小于 $2^{64}$，所以我们可以计算出每步操作后当前结果的最大范围来大幅减小每轮加法操作的重复次数，从而卡进要求的操作次数内。
### task 4
$(\operatorname{popcnt} a+\operatorname{popcnt} b) \bmod 2=\left(\operatorname{popcnt} (a\operatorname{xor} b)\right)\bmod 2$，所以我们每次讲 $x$ 拆成两部分异或起来直到剩下最后一位即可。
注意过程中可以不对前面位置清零，最后一次性清零来减小操作次数，另外最后一轮操作和前面略有不同（用来卡操作次数），需要微调。
另外过程中可以不使用右移而使用左移来把操作次数卡到 $24$（因为这样最后只需要一次右移，如果中间使用的是右移那么最后是需要一次左移和一次右移的）。
### task 5
首先我们默认 $a\neq b$，然后再考虑在 $a=b$ 时能不能正常工作。
求 $\min$ 的第一想法就是将两者逐位比较，所以我们会想到先将两者异或，求出异或结果中最高位的 $1$ 属于谁。
我们可以将 $a$ 跟异或的结果进行一次与运算，然后利用右移进行填充（可以利用倍增的思路来减小操作次数），使得与运算的结果从最高位的 $1$ 开始右边所有位置都被 $1$ 填满。
然后我们将其取反并再和之前异或的结果进行一次与运算，得到结果记为 $t$。此时如果得出的 $t=0$，那么说明最高位的 $1$ 是来自 $a$ 的，从而得出 $a>b$，否则反之。
再利用左移和右移将 $t$ 填充满（此时 $t$ 必定为 $0$ 或 $2^{64}-1$），对 $a$ 进行与运算。容易发现如果 $a>b$ 那么得到的结果就是 $0$，否则就是 $a$。
将 $t$ 取反后再对 $b$ 进行与运算，两次的结果进行或运算即可求出 $\min$。
最后检验一遍发现上面在 $a=b$ 时同样可以正常工作，所以直接按上面思路来即可。
### task 6
~~tm 搞个 $p=0$ 是个什么鬼。~~
考虑分成 $a\times b$ 和 $\bmod p$ 两部分处理。
因为我们已经有加法操作了，所以我们考虑对其中一个数从低到高拆位，从而将乘法分解成加法和 $\times 2$。这里建议对 $a$ 拆位。
问题变成如何判断对于每一位是否需要进行加法。
我们同样可以利用左移或右移来将这位的结果填满所有二进制位（也就是利用操作使得如果这位是 $1$，最后就会得到 $2^{64}-1$；如果是 $0$，最后就会得到 $0$）。完成上面操作后直接将所得的数对 $b$ 进行与运算即可得到这轮需要加上的数。
然后我们考虑取模。
因为模数是 $2$ 的非负整数次幂，所以我们可以利用与运算来取模。和上面类似，通过若干次右移和或运算得到用来进行与运算的数，将之前的结果和这个数进行与运算即可得到结果。
注意每次拆位完之后最好直接对当前位进行运算，这样不需要存贮结果，可以减少中间移动变量时的操作次数。另外因为过程中每次会对 $b\times 2$，这就意味着 $b$ 的最低位是不断升高的，可以利用这个来减小加法操作的重复次数。
### task 7
由题目条件可知 $a$ 必然为 $2$ 的偶数次幂或 $0$，直接每次取出两位即可。
### task 8
令 $a'=\min(a,b),b'=\max(a,b)$，有 $\gcd(a,b)=\gcd(a',b'-a')$。
通过 2 和 5 我们已经有了减法和求 $\min/\max$ 的操作（$\max$ 的操作可以直接在求 $\min$ 上稍作修改），直接套用即可。
另外实际上我们并不需要在这个点每轮重复 $64$ 次减法操作。因为 $a,b\leq 63$，所有计算结果都在 $2^6$ 内，所以只需要重复 $6$ 次即可。
代码（针对 task 8，不过里面也有其他 task 可能需要的操作的）：
```cpp
#include<bits/stdc++.h>
using namespace std;
void swa(){printf("xor 1\n"),printf("xor 0\n"),printf("xor 1\n");}//交换两个栈的栈顶
void sub(){printf("xor 0\n"),printf("and 1\n"),printf("lsh 1 1\n");}
int main()
{
freopen("8.out","w",stdout);
for(int tt=0;tt<64;tt++)
{
printf("xor 1\n"),printf("mov 0\n");
printf("xor 0\n"),printf("xor 1\n"),printf("mov 0\n");
printf("xor 0\n"),printf("mov 1\n");
printf("and 0\n");
printf("mov 0\n"),swa(),printf("mov 0\n");
for(int i=0;i<6;i++)
{
printf("or 0\n");
printf("rsh 0 %d\n",(1<<i));
if(i==5)printf("or 0\n");else printf("or 1\n");
}
printf("pop 1\n");
printf("not 0\n"),printf("and 0\n");
printf("rsh 1 64\n");
for(int i=0;i<6;i++)
{
printf("or 1\n");
printf("rsh 1 %d\n",(1<<i));
printf("or 0\n");
}
for(int i=0;i<6;i++)
{
printf("or 1\n");
printf("lsh 1 %d\n",(1<<i));
printf("or 0\n");
}
//以上为5时取min操作主体部分，后面为针对8调整的部分
printf("rsh 1 64\n"),printf("or 1\n");
printf("mov 0\n"),printf("xor 0\n");
printf("mov 0\n"),printf("xor 0\n");
printf("mov 1\n"),printf("mov 1\n"),printf("mov 1\n");
//左：4个t 右：a,b（从上到下）
printf("and 0\n"),swa(),printf("mov 0\n");
printf("not 0\n"),printf("and 0\n"),printf("pop 1\n");
printf("mov 1\n"),swa();
printf("mov 0\n"),swa(),printf("mov 0\n");
printf("and 0\n");
swa(),printf("mov 0\n");
printf("not 0\n"),printf("and 0\n"),printf("pop 1\n");
printf("mov 1\n");
//此时两栈栈顶从上往下第一个元素更新max，第二个元素更新min
printf("or 0\n"),printf("pop 1\n");
swa(),printf("mov 0\n");
printf("or 0\n"),printf("or 1\n");
printf("mov 1\n"),swa();
for(int i=0;i<6;i++)sub();
}
printf("mov 0\n");
}
```