题目分析

给定一个整数 ( n ) 和一个包含 ( m ) 个数字的集合，要求构造一个最小的非零整数，使得：

1. 该整数仅由集合中的数字组成；
2. 该整数能被 ( n ) 整除。

如果不存在这样的整数，输出 0。

解题思路

核心思想

使用 广度优先搜索（BFS） 来探索所有可能的数字组合，按数字长度递增的顺序检查是否能被 ( n ) 整除。BFS 保证一旦找到解，一定是最小的有效解。

关键步骤

1. 预处理：

   • 如果 ( n = 0 )，直接输出 0（因为任何数都能被 0 整除，但题目要求非零，矛盾）。
   • 检查集合中是否存在单个数字能直接被 ( n ) 整除（即 ( a_i \mod n == 0 )），若有则直接输出该数字。

2. BFS 初始化：

   • 队列中存储的数字是当前数值模 ( n ) 的结果（避免大数计算）。
   • 初始时，将集合中所有非零数字的个位数模 ( n ) 的结果入队。

3. BFS 扩展：

   • 每次从队列中取出一个数值 ( \text{val} )，尝试在其后追加集合中的每一个数字 ( d )，得到新数值 ( \text{val} \times 10 + d )。
   • 计算新数值模 ( n ) 的结果 ( \text{new_val} )。如果 ( \text{new_val} == 0 )，则找到解；否则若未访问过，则入队。

4. 输出结果：

   • 通过递归回溯路径，输出构造的数字。

解决代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 5005
using namespace std;

int n,m,ans;
int a[15];
bool vis[maxn];
struct Node
{
	int d;     // 当前节点所加的dight
	int val;   // 有效值
	int pre;   // 上一个节点编号
}cur,now,q[maxn];

bool bfs()
{
	int i,j,nx,tx;
	int head=0,tail=-1;
	memset(vis,0,sizeof(vis));
	cur.pre=-1;
	for(i=1;i<=m;i++)
	{
		if(a[i]!=0&&!vis[a[i]%n])
		{
			vis[a[i]%n]=1;
			cur.d=a[i];
			cur.val=a[i]%n;
			q[++tail]=cur;
		}
	}
	while(head<=tail)
	{
		nx=q[head].val;
		if(nx%n==0)
		{
			ans=head;
			return true;
		}
		for(i=1;i<=m;i++)
		{
			tx=nx*10+a[i];
			if(!vis[tx%n])
			{
				vis[tx%n]=1;
				cur.d=a[i];
				cur.pre=head;
				cur.val=tx%n;
				q[++tail]=cur;
			}
		}
		head++;
	}
	return false ;
}
void output(int k)       // 递归输出答案
{
	if(k==-1) return ;
	else
	{
		output(q[k].pre);
		printf("%d",q[k].d);
	}
}
int main()
{
	int i,j,flag;
	while(~scanf("%d",&n))
	{
		flag=0;
		scanf("%d",&m);
		for(i=1;i<=m;i++)
		{
			scanf("%d",&a[i]);
		}
		if(n==0)
		{
			printf("0\n");
			continue ;
		}
		sort(a+1,a+m+1);
		for(i=1;i<=m;i++)
		{
			if(a[i]%n==0&&a[i]!=0)
			{
				ans=a[i];
				flag=1;
				break ;
			}
		}
		if(flag)
		{
			printf("%d\n",ans);
			continue ;
		}
		if(bfs()) output(ans);
		else printf("0");
		printf("\n");
	}
	return 0;
}