ac1099.pas

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

program tju1099;
const
  maxt=100;
  maxm=100;
var
  prime:array[1..maxt]of word;
  ans:array[0..maxm]of string;
  e:array[1..maxt,1..maxm]of boolean;{boolean equations}
  t,m,x,i,j,k,exp:longint;
procedure calprime;
  var
    primes,x,i:word;
    ok:boolean;
  begin
    primes:=0;x:=1;
    repeat
      inc(x);
      ok:=true;
      for i:=1 to primes do
        if x mod prime[i]=0 then begin
          ok:=false;break;
        end;
      if ok then begin
        inc(primes);prime[primes]:=x;
      end;
    until primes=maxt;
  end;
procedure calans;
  var
    i,j:byte;
  begin
    ans[0]:='0';
    for i:=1 to maxm do begin
      ans[i]:='0';
      for j:=1 to length(ans[i-1]) do begin
        if ans[i-1,j]>'4' then inc(ans[i,length(ans[i])]);
        ans[i]:=ans[i]+chr(48+(ord(ans[i-1,j])-48)*2 mod 10);
      end;
      inc(ans[i,length(ans[i])]);
      if ans[i,1]='0' then delete(ans[i],1,1);
    end;
  end;
begin
  calprime;
  calans;

  repeat
    fillchar(e,sizeof(e),0);
    read(t,m);
    for i:=1 to m do begin
      read(x);
      for j:=1 to t do begin
        while x mod prime[j]=0 do begin
          e[j,i]:=not e[j,i];
          x:=x div prime[j];
        end;
        if x=1 then break;
      end;
    end;

    exp:=0;
    for i:=m downto 1 do begin
      x:=0;
      for j:=1 to t do
        if e[j,i] then begin
          x:=j;break;
        end;
      if x=0 then inc(exp) else begin
        for j:=1 to t do
          if (j<>x) and e[j,i] then
            for k:=1 to i do
              e[j,k]:=e[j,k]<>e[x,i];
        e[x]:=e[t];
        dec(t);
      end;
    end;
    writeln(ans[exp]);
  until seekeof;
end.