SPOJ – CRYPTKEY

Đề bài: http://vn.spoj.com/problems/CRYPTKEY/

Thuật toán:

• (đang cập nhập)

Code

const
  fi='';
  fo='';
  maxn=50003;
var
  a : array[1..maxn] of int64;
  b : array[1..maxn] of int64;
  c : array[1..100000] of int64;
  uoc : array[1..100000] of int64;
  sl : array[1..100000] of longint;
  i,j,n,t,tt : longint;
  duoc : longint;
  kt : boolean;
  res,k : int64;
procedure enter;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
end;
procedure pt(x : int64);
  var i,j,dem : longint;
  begin
    for i:=2 to trunc(sqrt(x)) do
      if x mod i = 0 then
        begin
          dem := 0;
          while x mod i = 0 do
            begin
              inc(dem);
              x := x div i;
            end;
          duoc := duoc +1;
          uoc[duoc] := i;
          sl[duoc] := dem;
        end;
    if x>1 then
      begin
        inc(duoc);
        uoc[duoc] := x;
        sl[duoc] := 1;
      end;
  end;
function power(x,y:longint):int64;
  var i : longint;
  begin
    power:=1;
    for i:=1 to y do power := power * x;
  end;
function gcd(a,b : int64) : int64;
  var r : int64;
  begin
      while b<>0 do
        begin
          r := a mod b;
          a:=b;
          b:=r;
        end;
      exit(a);
  end;
function lcm(a,b : int64) : int64;
  var x,y : int64;
  begin
    {x := a; y:=b;}
    lcm := (a div gcd(a,b)) *b;
  end;
procedure sol;
var i,j : longint;
    tg : int64;
    dem : longint;
begin
  read(t);
  for tt :=1 to t do
    begin
      fillchar(a,sizeof(a),0);
      fillchar(uoc,sizeof(uoc),0);
      fillchar(sl,sizeof(sl),0);
      kt := true;
      read(n);
      for i:=1 to n do read(a[i]);
      readln(k);
      pt(k);
      for i:=1 to duoc do
      begin
        tg := power(uoc[i],sl[i]);
        dem := 0;
        for j:=1 to n do
          if a[j] mod tg = 0 then
           begin
             inc(dem); b[dem] := a[j];
           end;
        if dem=0 then begin kt := false; break; end;
        tg := b[1];
        for j:=2 to dem do
          tg := gcd(tg,b[j]);
        c[i] := tg;
      end;
      if not kt then begin writeln('NO'); continue; end;
      res := c[1];
      for i:=2 to duoc do res := lcm(res,c[i]);
      if res=k then
      writeln('YES') else writeln('NO');
    end;
  close(input);close(output);
end;
begin
  enter;
  sol;
end.