BLGEN – spoj

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

Thuật toán:

• (đang cập nhập)

Code:

uses math;
const   fi      ='';
        fo      ='';
        oo      =1000;
        maxc    =trunc(3e6);
var     n       :array[1..2] of longint;
        a       :array[1..2,1..1000] of qword;
        f       :array[0..oo,0..oo] of longint;
        mp      :longint;
        g       :array[1..maxc] of longint;
        nto     :Array[1..300000] of qword;
procedure nhap;
var     i :longint;
        k :longint;
        p :qword;
begin
        assign(input,fi);
        reset(input);
                k:=0;
                while not seekeof() do
                begin
                        inc(k);
                        while not seekeoln() do
                        begin
                                inc(n[k]);
                                read(p);
                                a[k,n[k]]:=p;
                        end;
                        readln;
                end;
        close(input);
end;
procedure sang;
var     i,j     :longint;
begin
        for i:=2 to trunc(sqrt(maxc)) do
        if g[i]=0 then
        begin
                j:=i*I;
                while j<=maxc do
                begin
                        g[j]:=i;
                        inc(j,i);
                end;
        end;
        for i:=2 to maxc do
        if g[i]=0 then
        begin
                inc(mp);
                nto[mp]:=i;
        end;
end;
function find(x:qword):boolean;
var     d,c,mid   :longint;
        t1,t2,t3      :qword;
begin
        d:=1; c:=mp;
        while d<=c do
        begin
                mid:=(d+c) div 2;
                t1:=x mod nto[mid];
                t2:=x div nto[mid];
                t3:=nto[mid]*nto[mid];
                if (t1=0) and (t2=t3) then exit(true);
                if (t3>t2) then c:=mid-1
                else d:=mid+1;
        end;
        exit(false);
end;
function kt(x:qword):boolean;
var     x1      :qword;
begin
        x1:=trunc(sqrt(x));
        if x1*x1=x then exit(true);
        if find(x) then exit(true);
        exit(false);
end;
procedure xuli;
var     i,j     :longint;
begin
        for i:=1 to n[1] do
        for j:=1 to n[2] do
        if (a[1,i]=a[2,j]) and kt(a[1,i]) then f[i,j]:=f[i-1,j-1]+1
        else f[i,j]:=max(f[i-1,j],f[i,j-1]);
end;
procedure xuat;
begin
        assign(output,fo);
        rewrite(output);
                writeln(f[n[1],n[2]]);
        close(Output);
end;
begin
        nhap;
        sang;
        xuli;
        xuat;
end.