题解 | #Sramoc问题#
Sramoc问题
https://ac.nowcoder.com/acm/problem/235247
链接: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;
}