NKPATH - Đường đi trên lưới
Tác giả: RR
Ngôn ngữ: Pascal
const
base=1000000000;
var
res,p,q,i,j,m,n:longint;
f,a:array[1..111,1..111] of longint;
function gcd(a,b:longint):longint;
begin
if (a=0) or (b=0) then exit(a+b)
else exit(gcd(b,a mod b));
end;
begin
read(m,n);
for i:=1 to m do
for j:=1 to n do
read(a[i,j]);
for i:=1 to m do
f[i,1]:=1;
for p:=1 to m do
for q:=1 to n do
for i:=1 to p do
for j:=1 to q do
if j<n then
if (i+j<p+q) and (gcd(a[i,j],a[p,q])>1) then
begin
inc(f[p,q],f[i,j]);
if f[p,q]>base then dec(f[p,q],base);
end;
res:=0;
for i:=1 to m do
begin
res:=res+f[i,n];
if res>base then dec(res,base);
end;
writeln(res);
end.