題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF2109C3. Hacking Numbers (Hard Version)

tags: `構造(Constructive)` `互動題(Interactive)` `數學(Math)` `數論(Number Theory)`

題意

題目分為三個版本，在 Easy 版本中，最多只能操作 $7$ 次；在 Medium 版本中，最多只能操作 $4$ 次；在 Hard 版本中，最多只能操作 $f(n)$ 次，其中 $f(n)$ 是對於任意的 $x$ 都可以使操作成立的最小操作次數。

存在一個未知的整數 $x$ ，必須透過以下操作將其變成輸入中給定的整數 $n$ ：

add y： $x \leftarrow x + y$ $x \leftarrow x + y$
- $-10^{18} \le y \le 10^{18}$
mul y： $x \leftarrow x \cdot y$ $x \leftarrow x \cdot y$
- $1 \le y \le 10^{18}$
div y： $x \leftarrow x / y$ $x \leftarrow x / y$
- $1 \le y \le 10^{18}$
digit： $x \leftarrow S(x)$ ，其中 $S(x)$ 是 $x$ 的每一位數字之和。

但操作存在以下限制：

對於 add 和 mul 操作，如果結果不在 $[1, 10^{18}]$ 的範圍，則不會進行更新，且會回傳 0。
對於 div 操作，如果 $y$ 不能整除 $x$ ，則不會進行更新。

約束條件

$1 \le n, x \le 10^9$

思路：數學魔術

初步想法 (5 次操作)

由於起始的數字 $x$ 是未知的，我們的策略必須對所有在 $[1, 10^9]$ 範圍內的 $x$ 都有效。這意味著我們需要找到一個操作序列，能將任何合法的 $x$ 都轉換成一個固定的、已知的常數。一旦得到了一個常數 $C$ ，問題就變得非常簡單：只需要再執行一次 add n - C 操作就能達到目標 $n$ 。

由於 $x$ 的位數是已知的，一個初步的想法是將 $x$ 的每位都補成 $9$ ，舉例來說，如果 $x = 123456789$ ，則可以在右邊補上 $876543210$ ，即 $123456789876543210$ ，這樣每兩兩一對的數位和都變成 $9$ 。

$\begin{aligned} &123456789 \\ + &876543210 \\ \hline &999999999 \end{aligned}$

根據上述想法，對於 $d$ 位數 $y \isin [0, 10^d - 1]$ ，可以用 $y \cdot 10^d + \underbrace{999...999}_{d\text{個}} - y$ ，來構造出一個 digit sum 為 $9 \cdot d$ 的數字，此式可以寫成 $y \cdot (10^d - 1) + (10^d - 1)$ 。

對於任意的 $d$ 位數 $y \isin [0, 10^d - 1]$ ，可以用 $y \cdot (10^d - 1) + (10^d - 1)$ ，來使操作後的 digit sum 為 $9 \cdot d$ 。

但因為題目給定的 $x \isin [1, 10^9]$ ，是 $10$ 位數，直接用 $d = 10$ 會遇到操作失敗的問題，所以先做 $-1$ 操作，就可以使 $d = 9$ ，此時需要 $5$ 次操作，只能通過 C1。

add -1
mul 999999999
add 999999999
digit
add n - 81

優化 (3 次操作)

將 $y = (x - 1)$ 重新代入，可以得到：

$\begin{aligned} &y \cdot 10^d + (10^d - 1) - y \\ = &(x - 1) \cdot 10^d + (10^d - 1) - (x - 1) \\ = &x \cdot (10^d - 1) \\ \end{aligned}$

對於任意的 $x \isin [1, 10^d]$ ，可以用 $x \cdot (10^d - 1)$ ，來使操作後的 digit sum 為 $9 \cdot d$ 。

此時我們可以將前 $3$ 次操作替換為 $1$ 次，總共只需要 $3$ 次操作，可以過 C2/C3。

注意 C3 在 $n = 81$ 時可以省略最後一個操作。

mul 999999999
digit
add n - 81

完整程式碼

import sys
input = sys.stdin.readline
def ans(*args):
    print(*args if len(args) else "!", flush=True)
    return int(input())

t = int(input())
for _ in range(t):
    n = int(input())
    ans("mul", 999999999)
    ans("digit")
    if n != 81:
        ans("add", n - 81)
    ans()

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG, unified 8k wallpaper, High Detail, vibrant colors, anime style, official art, illustration, perfect scenery, perfect environment, depth of field, sharp focus, Scenery,

1girl, solo, castorice (honkai star rail), bright lilac eyes, purple eyes, very long hair, lavender thigh-length hair, lavender hair, light purple hair, pointy ears, large breasts, cleavage, purple butterfly clips, head wreath, gloves, purple gloves, white dress, dress, standing in a dreamy field of luminous purple flowers at dusk, surrounded by glowing butterflies, holding her hands out gracefully as butterflies flutter around her, dramatic twilight sky with shooting stars, magical and ethereal atmosphere, soft glowing light, distant mountains in the background,

A beautiful anime girl with long lavender hair and pointy ears stands in a glowing field of purple flowers at dusk, her elegant white dress adorned with butterfly and flower motifs. She holds her hands out as luminous butterflies dance around her, under a dramatic twilight sky filled with shooting stars and distant mountains, creating a magical and ethereal scene.