题解 | #Sramoc问题#

链接：https://ac.nowcoder.com/acm/problem/235247 来源：牛客网

Sramoc(K,M) 表示用数字0,1,2,3,4,...,k−10,1,2,3,4,...,k-10,1,2,3,4,...,k−1组成的自然数中能被M整除的最小数。给定K,MK,MK,M2≤K≤10,1≤M≤10002\leq K\leq 10,1\leq M\leq 10002≤K≤10,1≤M≤1000，求Sramoc(K,M)Sramoc(K ,M)Sramoc(K,M)。例如K=2,M=7K=2,M=7K=2,M=7的时候,Sramoc(2,7)=1001Sramoc(2 ,7) =1001Sramoc(2,7)=1001。

做法

从1到k-1每一位出发，去广搜是否能被m整除，如果有一个数的模数已经出现过，说明已经有一个更小的数满足，直接丢弃，再根据取余的性质，若一个数的模数为x，在后面增加一位a，模数变为（x*10+a）%m，这样保证不会超过m得到一个很大的数，因为是广搜，遇到模数为0的直接输出即可。

//本题代码
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
//dont forget to check long long
struct node{
    std::string s;
    int yu;
};
int k,m;
bool vis[101000];
std::queue<node> q;
std::string bfs(std::string s)
{
   
    memset(vis,false,sizeof(vis));
    for(int i=1;i<k;i++)
    {
        std::string s="";
        s+=(i+'0');
        if(vis[i%m]==0) q.push({s,i%m});
        vis[i%m]=true;
    }
    while(!q.empty())
    {
        node tmp=q.front();
        q.pop();
        if(tmp.yu==0) return tmp.s;
        for(int i=0;i<k;i++)
        {
            node cur=tmp;
            cur.yu=(cur.yu*10+i)%m;
            if(!vis[cur.yu])
            {
                cur.s+=(i+'0');
                vis[cur.yu]=true;
                q.push({cur.s,cur.yu});
            }
        }
    }
    return 0;
}
void slove()
{
     
     std::cin>>k>>m;
     std::cout<<bfs("1");

}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T=1;
    //std::cin>>T;
    while(T--)
    {
        slove();
    }

    return 0;
}