题意

• 给定k,m,构造一个由0~k-1这些数字组成的数，使得k整除m

思路

• 利用同余，不断广搜，一个余数出现后，后面再出现相同余数就直接跳过
• 开始要从1~k的每一个值都试一遍
• 由于位数很多，需要使用字符串来存储数字

AC代码

#include <bits/stdc++.h>

using namespace std;

int k, m;
bool vis[1007];
struct node {
    string num;
    int r;
};
string bfs() {
    queue<node> q;
    for (int i = 1;i < k;i++) {
        string s(1, '0' + i);
        q.push({ s,i % m });
        vis[i % m] = 1;
    }
    while (!q.empty()) {
        node cur = q.front();
        q.pop();
        if (!cur.r) return cur.num;
        for (int i = 0;i < k;i++) {
            string s(1, '0' + i);
            string nnum = cur.num + s;
            int rr = (cur.r * 10 + i) % m;
            if (vis[rr]) continue;
            vis[rr] = 1;
            q.push({ nnum,rr });
        }
    }
    return "null";
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> k >> m;
    cout << bfs() << '\n';
    return 0;
}

字符串如何定义

• 对于该题初始的k个单字符串，可以采用字符串的重复构造法
• string s(count,char);构建长为count的重复char字符串