题意

原题链接

中文简化版：

本题为交互题。

交互库保存一个隐藏的变量 ，最开始保证 为 以内的整数；你需要经过若干次操作使得它变为给定的 ，保证 为 以内的整数。

如果操作失败，交互库会告知你，但是仍然消耗一次操作机会。

提交答案不消耗操作机会。

Command	Constraint	Result	Case	Update	response
add y					1
					0
mul y					1
					0
div y			divides		1
					0
digit	—		—		1

：这里 表示求 的 进制下的各位数字和，例如 。

• Easy: 次操作；
• Medium： 次操作；
• Hard：最优化操作次数。

Algo 0: 31 op

首先想到二分，考虑不断从 中减去 ，由于 ，因此只需减 次即可将 变为 。最后乘 即可。

Algo 1: 7 op

然后考虑使用 函数，使用 次后值域缩小到 ，再使用 次后值域缩小到 ，因此再减 次即可减到 。

Algo 2: 4 op

回想我们小学二年级学过的 的整除性判定，考虑再先乘 。这样再取一次 函数后，结果只会为 中的一个。

再取一次 函数， 变为 ，下一步加 即可。

Algo 3: 2~3 op

注意到：

这是因为：

因此，我们只需要在最开始乘 ，接着取 函数，答案一定为 。

若 ，则已经做完，使用 次操作。

否则，再加 ，共使用 次操作。

最优性证明

容易证明，至少花费 次操作，才能使 变成某一个确定的数。

因此，只需证，经过 次操作，将 变为一个确定的数，则这个数一定为 。

首先，容易证明至少需要一次 操作，因为其他每种操作都最多将值域缩小一半。

其次，不能连用两次 操作，因为此时值域为 。

再次，第一次操作不能为 操作，原因同样是其他每种操作都最多将值域缩小一半。

最后，考虑第一次操作的类型。

由于 恒成立，而 操作和 操作必定剩下相邻的数，因此第一次操作必须为 。

假设存在 使得 为常数，考虑 和 ：

综上所述，只有先乘 ，再取 函数，才能使 变为定值，且定值为 。