ac1040.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1040;
const
  maxn=4999;
var
  ok:array[0..9]of boolean;
  q,pre:array[1..maxn]of word;
  digit:array[1..maxn]of byte;
  v:array[0..maxn-1]of boolean;
  k,u,n,m,i,f,r:word;
procedure out(p:word);
  begin
    if p>1 then begin
      out(pre[p]);
      write(digit[p]);
    end;
  end;
procedure bfs;
  begin
    fillchar(v,sizeof(v),0);
    f:=0;r:=1;q[1]:=0;
    repeat
      inc(f);
      for i:=ord(q[f]=0) to 9 do
        if ok[i] then begin
          m:=(q[f]*10+i) mod n;
          if not v[m] then begin
            inc(r);q[r]:=m;pre[r]:=f;digit[r]:=i;v[m]:=true;
            if m=0 then begin out(r);writeln;exit;end;
          end;
        end;
    until f=r;
    writeln('0');
  end;
begin
  read(k);
  for u:=1 to k do begin
    read(n,m);
    fillchar(ok,sizeof(ok),0);
    for i:=1 to m do begin
      read(f);
      ok[f]:=true;
    end;
    bfs;
  end;
end.