NKPATH - Đường đi trên lưới
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
fo='';
z=1000000000;
maxn=101;
var n,m,re:longint;
a,f:array[1..maxn,1..maxn] of longint;
procedure rf;
var i,j:longint;
begin
readln(m,n);
for i:=1 to m do
for j:=1 to n do
read(a[i,j]);
end;
function gcd(x,y:longint):boolean;
begin
gcd:=true;
if x*y=0 then
begin
gcd:=(x+y)<>1;
exit;
end;
if (x and 1) or (y and 1)=0 then exit;
if x>y then gcd:=gcd(x mod y,y)
else gcd:=gcd(x,y mod x);
end;
procedure pr;
var i,j,u,v:longint;
begin
for i:=1 to m do f[i,1]:=1;
for j:=1 to n do
for i:=1 to m do
begin
for v:=1 to j-1 do
for u:=1 to i do
if gcd(a[i,j],a[u,v]) then
begin
f[i,j]:=f[i,j]+f[u,v];
if f[i,j]>=z then f[i,j]:=f[i,j]-z;
end;
if j<n then
for u:=1 to i-1 do
if gcd(a[i,j],a[u,j]) then
begin
f[i,j]:=f[i,j]+f[u,j];
if f[i,j]>=z then f[i,j]:=f[i,j]-z;
end;
end;
end;
procedure wf;
var i:longint;
begin
re:=0;
for i:=1 to m do
begin
re:=re+f[i,n];
if re>=z then re:=re-z;
end;
writeln(re);
end;
begin
assign(input,fi); reset(input);
assign(output,fo); rewrite(output);
rf;
pr;
wf;
close(input); close(output);
end.