SPOJ – CRYPTKEY

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.

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.