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.

Download