题目分析

题意简述

给定两个一位数 $n$ 和 $k$（$1 \leq n, k \leq 9$），寻找最小的 $n$-戏剧数，即满足以下条件的数：

1. 当该数乘以 $n$ 时，其最右边的数字会移动到最左边
2. 该数的最后一位必须为 $k$
3. 如果不存在这样的数，输出 $0$

输入

• 第一行输入测试用例数量 $t$
• 每个测试用例包含两个整数 $n$ 和 $k$

输出

• 对于每个测试用例，输出满足条件的最小数字（若无解则输出 $0$）

---

解题思路

数字变换特性

$n$-戏剧数的核心特征是：

$$n \times \overline{d_1d_2...d_m} = \overline{d_md_1d_2...d_{m-1}} $$

其中 $d_m = k$（最后一位固定为 $k$）

递归构造法

1. 终止条件：当构造的数字首位为 $k$ 且无进位时，找到解
2. 递归过程：
   • 计算当前位 $a \times n + \text{进位}$
   • 保留个位数作为新数字的一位
   • 将十位数作为新的进位继续递归

边界处理

• 当 $n > k$ 时直接返回 $0$（因为 $n \times \text{末位} \geq n > k$，无法满足首位为 $k$）
• 通过 flag 标记控制数字的生成顺序

---

代码实现

#include <cstdio>
#include <cstdlib>
#include <cstring>

int t, N, K, flag;

void work(int a, int b, int p) {
    int ans = a * b + p;
    // 终止条件：首位为K且无进位
    if (a == K && !p && flag) return;  
    flag = 1;
    // 递归处理下一位
    work(ans % 10, b, ans / 10);  
    // 逆序输出数字
    if (!flag) printf("%d", ans % 10);  
    else flag = 0;
}

int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d", &N, &K);
        if (N > K) puts("0");  // 无解情况
        else {
            work(K, N, 0);      // 从末位K开始构造
            printf("%d\n", K);  // 补全末位
        }
    }
    return 0;
}

代码说明

1. 核心函数 work

   • 参数：当前数字 $a$、乘数 $b$、进位 $p$
   • 递归生成数字的每一位，满足 $n \times \text{原数} = \text{循环右移数}$

2. 输出控制

   • 通过 flag 确保数字从高位到低位正确输出
   • 最后补上固定的末位 $k$

3. 复杂度分析

   • 时间复杂度：$O(m)$，其中 $m$ 为结果数字的位数
   • 空间复杂度：$O(m)$（递归栈深度）