题解：P10400 『STA - R5』消失的计算机

liuli688 · 2024-05-08 13:12:44 · 题解

前置部分

我的编号方法

在代码里可能会出现一些特殊编号，解释如下。

• ### 基础操作
• 想象一下，如果是在正常语言里，你会写 `n += p[x]` 或 `n := n + p[x]`。可是这种语言一次只能加 $1$，怎么办？ 由于一次只能加 $1$，那么方法显然是将 $p_x$ 拆成 $p_x$ 个 $1$。那么写法应该很明确了： ``` dec x new 999 ifneq x 1000 goto 1 ``` 不过，前提是 $p_x > 0$。如果 $p_x$ 小于 $0$ ，增加 $-p_x$ 次，那么应当这么写： ``` dec y new 999 ifneq x y goto 1 ``` 其中 $y$ 是任意一个空变量。其实这很像减法。 - $n \gets n \times p_x$： 只要嵌套两层加法即可。 ``` dec 1 assign 2 x dec 2 new 999 ifneq 2 1000 goto 3 ifneq 1 1000 goto 1 ```
• 取模似乎比较难。不过我们仔细想一想，取模就是得到这个数的余数，所以我们需要进行除法。那么，除法怎么做？回想一下，应该是将 $n$ 重复减 $p_x$，直到 $n < 0$。 所以，我们便可以用刚才的加法（减法）来求解了。 ``` assign 2 1000 dec 2 dec 1 ifneq 2 x goto 2 iftry 1 goto 1 new 999 dec 3 ifeq 1 3 goto 6 ``` 其中 $p_x$ 为模数的相反数。即这段代码实现的功能是 $n \gets n \bmod -p_x$。 ### 注意事项

• iftry 是大于等于 0，ifeq x 1000 是等于 0，请注意区分。

• 增加和输出是两个不同的概念。如果要增加 x，那么应该输出 n+x。

• ## 思路 & 代码 ### Task 1 $2n$ 即 $n + n$，直接使用前置部分的加法即可。 ``` 3 dec 1 new 2 ifneq 1 1000 goto 1 ``` ### Task 2 原式 $= 1 + 2 + \dots + (n-1)$。由于是**输出**，所以 $n$ 应增加 $2 + 3 + \dots + (n-2)$。可是这样不好循环怎么办？我们只需将每个数减 $1$，然后用 `iftry` 代替 `ifneq x 1000` 即可把循环次数补回来。 ``` 9 dec 1 dec 1 dec 1 assign 2 1 dec 2 new 999 iftry 2 goto 5 dec 1 ifneq 1 1000 goto 4 ``` ### Task 3 注意到 $5 \le n \le 100$。那么，我们应让 $n$ 增加 $600 - n$。所以，问题便转换成构造 $600 - n$。那么这不就是一个减法问题吗？只要构造 $600$ 即可。$600$ 可以通过循环，用 $2^3 \times 3 \times 5^2$ 构成。

爆标 199 行。

34
dec 12
dec 12
dec 13
dec 13
dec 13
dec 15
dec 15
dec 15
dec 15
dec 15
dec 2
assign 3 1000
dec 3
assign 4 1000
dec 4
assign 5 1000
dec 5
assign 6 1000
dec 6
assign 7 1000
dec 7
dec 10
ifneq 7 15 goto 21
ifneq 6 15 goto 19
ifneq 5 13 goto 17
ifneq 4 12 goto 15
ifneq 3 12 goto 13
ifneq 2 12 goto 11
dec 1
dec 11
ifneq 1 1000 goto 29
new 999
dec 11
ifneq 10 11 goto 32

Task 4

不用多说。

1
new 1

Task 5

分解 n^2 - 1，得 (n+1)(n-1)。由于也是输出，所以式子应减 n，变为 (n+1)(n-2) + 1。于是使用乘法，问题就十分简单了。

10
assign 3 1
dec 3
dec 3
new 1
dec 1
assign 2 3
new 4
dec 2
ifneq 2 1000 goto 7
ifneq 1 1000 goto 5

Task 6

最简单的办法是 new 2000 次，但是行数显然超标，所以难点在于构造 2000（实际是 -2000）。2000 = 2^4 \times 5^3，为使行数最少，我决定用 4^2 \times 5^3 来构造。

爆标 5 行。

24
dec 14
dec 14
dec 14
dec 14
dec 15
dec 15
dec 15
dec 15
dec 15
dec 2
assign 3 1000
dec 3
assign 4 1000
dec 4
assign 5 1000
dec 5
assign 6 1000
new 1
dec 6
ifneq 6 15 goto 18
ifneq 5 15 goto 16
ifneq 4 15 goto 14
ifneq 3 14 goto 12
ifneq 2 14 goto 10

Task 7

还原求 \log 的场景。用变量记录底数，n 增加指数个， 若计数器数量到达底数则底数翻倍，n \gets n + 1。

爆标 1 行。

13
dec 1
dec 1
dec 2
dec 2
assign 12 2
assign 10 1000
dec 12
dec 10
dec 1
ifneq 10 2 goto 7
new 999
assign 2 12
iftry 1 goto 5

Task 8

套用前置部分的取模即可。

爆标 1 行。

6
dec 1
dec 1
iftry 1 goto 1
new 3
dec 2
ifeq 1 2 goto 4

Task 9

分类讨论。

• 当 n \bmod 4 = 0 时，\gcd(n,n-4) = 4。
• 当 n \bmod 4 = 1 时，\gcd(n,n-4) = 1。
• 当 n \bmod 4 = 2 时，\gcd(n,n-4) = 2。
• 当 n \bmod 4 = 3 时，\gcd(n,n-4) = 1。

所以，我们只要用 Task 8 的方法求出模数，再判断：用一个循环分离奇偶数，再用一个循环分离 2 和 4。

18
dec 1
dec 1
dec 1
dec 1
assign 2 1
dec 2
iftry 2 goto 1
dec 12
dec 12
assign 14 12
dec 14
dec 14
new 999
new 999
dec 1
dec 1
ifeq 1 14 goto 14
ifeq 1 12 goto 13

Task 10

首先想到的是构造与 n \operatorname{ln} n 尽可能相近的数，为 n \log_3 n。可是这样还是有误差，那么再加常数，得 n \log_3 n + 16（因为 16 = 2^4）。可是行数超标。

我们将 n \operatorname{ln} n 打出表来，发现相邻两数的差变化不大，这提醒我们可以用形如 y = kx 的值来求解。经过尝试，发现在 4 至 5 范围内比较接近。最终我使用 y = \frac {13n} 3。凑 4 非常简单，凑 \frac n 3 则用除法求出近似值即可。

14
dec 13
dec 13
dec 13
dec 3
assign 2 1
dec 2
new 999
ifneq 2 1000 goto 6
ifneq 3 13 goto 4
dec 1
dec 1
dec 1
new 999
iftry 1 goto 10

于是便完美地 A 掉这道题啦！