最小不同数字倍数问题题解

一、题目分析

题目要求找到正整数n的倍数m，使得m的十进制表示中不同数字的数量最少。若有多个解，输出数值最小的m。例如：

• 输入7，输出7（仅含数字7）；
• 输入15，输出555（仅含数字5）。

二、算法思路

1. 广度优先搜索（BFS）：

   • 按不同数字数量从小到大搜索（先搜1个数字，再搜2个数字，依此类推）；
   • 每个状态记录当前余数、位数、路径，避免重复计算。

2. 剪枝优化：

   • 若当前状态的位数已超过已知最优解，提前终止；
   • 使用余数判重，避免处理重复状态。

3. 字典序处理：

   • 按数字组合的字典序生成候选集，确保找到的解为数值最小。

三、代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define maxn 65540
using namespace std;

int n, m, mcnt, tcnt, h;
int a[5];
bool vis[maxn];  // 记录余数是否已访问，避免重复计算
string ans, tans;  // 存储最终答案和临时答案

struct Node {
    int d, val, pre;  // d:当前位数字，val:当前余数，pre:父节点索引
    int cnt;  // 位数
} cur, now, q[maxn];  // BFS队列

// 递归构建答案字符串
void getans(int k) {
    if (k == -1) return;
    getans(q[k].pre);
    tans += (char)(q[k].d + '0');
}

// BFS搜索，使用k个不同数字
bool bfs(int k) {
    int head = 0, tail = -1;
    memset(vis, 0, sizeof(vis));
    
    // 初始化队列，处理首位非零的情况
    for (int i = 1; i <= k; i++) {
        if (a[i] != 0) {
            cur.cnt = 1;
            cur.d = a[i];
            cur.pre = -1;
            cur.val = a[i] % n;
            vis[cur.val] = true;
            q[++tail] = cur;
        }
    }
    
    while (head <= tail) {
        now = q[head];
        if (now.cnt > mcnt) break;  // 剪枝：超过已知最优解位数
        
        if (now.val == 0) {  // 找到余数为0的解
            h = head;
            tcnt = now.cnt;
            return true;
        }
        
        // 扩展状态
        for (int i = 1; i <= k; i++) {
            int tval = (now.val * 10 + a[i]) % n;
            if (!vis[tval]) {
                vis[tval] = true;
                cur.cnt = now.cnt + 1;
                cur.d = a[i];
                cur.pre = head;
                cur.val = tval;
                q[++tail] = cur;
            }
        }
        head++;
    }
    return false;
}

int main() {
    while (scanf("%d", &n) && n != 0) {
        int flag = 0;
        ans = "xx";  // 初始化为大值
        mcnt = 1e9;  // 初始最小位数为极大值
        
        // 尝试用1个数字构造解
        for (int i = 1; i <= 9; i++) {
            a[1] = i;
            if (bfs(1)) {
                tans = "";
                getans(h);
                if (mcnt > tcnt || (mcnt == tcnt && ans > tans)) {
                    ans = tans;
                    mcnt = tcnt;
                }
            }
        }
        
        // 若找到解，输出并处理下一个测试用例
        if (ans != "xx") {
            flag = 1;
            cout << ans << endl;
        }
        
        // 若1个数字无解，尝试用2个数字构造解
        if (!flag) {
            for (int i = 0; i <= 9; i++) {
                a[1] = i;
                for (int j = i + 1; j <= 9; j++) {
                    a[2] = j;
                    if (bfs(2)) {
                        tans = "";
                        getans(h);
                        if (mcnt > tcnt || (mcnt == tcnt && ans > tans)) {
                            ans = tans;
                            mcnt = tcnt;
                        }
                    }
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}

四、代码解释

1. 数据结构：

   • Node结构体记录当前状态（余数、位数、路径）；
   • vis数组记录余数是否已访问，避免重复处理。

2. BFS搜索：

   • 初始化队列时处理首位非零的情况；
   • 每次扩展状态时，检查新余数是否已访问，避免循环；
   • 找到余数为0的状态时，记录路径并返回。

3. 答案构造：

   • getans函数递归构造答案字符串，确保按正确顺序拼接数字；
   • 按字典序生成候选数字组合，确保优先找到数值最小的解。

五、示例解析

输入：15

1. 搜索1个数字：尝试1-9，均无法整除15；
2. 搜索2个数字：按字典序尝试组合（0,1）、（0,2）等，找到555（仅含数字5），满足条件。
3. 输出：555

六、复杂度分析

• 时间复杂度：最坏情况O(n×10)，其中n为输入数值；
• 空间复杂度：O(n)，主要用于存储余数判重数组和BFS队列。

七、关键技巧

1. 余数判重：利用模运算特性，避免处理重复余数状态；
2. 字典序生成：按顺序生成候选数字组合，确保优先找到最小数值解；
3. 剪枝优化：提前终止超过已知最优解位数的状态，减少搜索空间。