POJ 1465 Multiple

問題

与えられたm個の数字x1,x2,...,xmのみを使ってできる、最小のNの倍数を求めよ。
作れない場合は0を出力せよ。

制約条件

m個の数字は全て異なる。
0≦N≦5000

方針

先頭から数字を決めていく幅優先探索+経路復元。
余りをメモ化しておき、同じ余りが出てきたら探索を打ち切る。

あらかじめ数字を昇順にソートしておくことにより、
最初に得られた答えが、最小のNの倍数になっている。

N=0の場合を特別に処理をしないとゼロ除算でRuntime Errorになる。

ソースコード

int n,m,x[10];
int prev[5000], use[5000];
char ans[5000];

int main()
{
	while(~scanf("%d",&n)){
		scanf("%d",&m);
		rep(i,m)scanf("%d",x+i);
		sort(x,x+m);
		
		if(!n){
			puts("0"); continue;
		}
		
		queue<int> q;
		rep(i,n)prev[i]=-1;
		rep(i,m)if(x[i])q.push(x[i]%n), prev[x[i]%n]=-2, use[x[i]%n]=x[i];
		
		while(!q.empty()){
			int c=q.front(); q.pop();
			if(c==0){
				int len=0;
				for(;c>=0;c=prev[c])ans[len++]='0'+use[c];
				ans[len]=0;
				reverse(ans,ans+len);
				puts(ans);
				goto END;
			}
			rep(i,m){
				int next=(c*10+x[i])%n;
				if(prev[next]==-1)use[next]=x[i], prev[next]=c, q.push(next);
			}
		}
		puts("0"); END:;
	}
	return 0;
}