Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

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.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 105
#define MOD 1000000000

int f[N][N], a[N][N], m, n;

int gcd(int a, int b) {
    int t;
    while(b) { t = b; b = a % t; a = t; }
    return a;
}

int main() {
    //freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
    scanf("%d%d",&m,&n);
    rep(i,m) rep(j,n) scanf("%d",&a[i][j]);
    rep(i,m) f[i][0] = 1;
    rep(i,m) rep(j,n) rep(x,i+1) rep(y,j+1) 
        if( y < n-1 && x+y < i+j && gcd(a[x][y], a[i][j]) != 1) 
            f[i][j] = (f[i][j] + f[x][y]) % MOD;
    int res = 0; rep(i,m) res = (res + f[i][n-1])%MOD;
    printf("%d\n", res);
    return 0;
}

Code mẫu của ladpro98

program nkpath;
uses    math;
const   fi='';
        maxN=111;
        base=trunc(1e9);
var     a:array[1..maxN,1..maxN] of longint;
        f:array[1..maxN,1..maxN] of longint;
        m,n,res:longint;

procedure input;
var     inp:text;
        i,j:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,m,n);
        for i:=1 to m do
        for j:=1 to n do
        read(inp,a[i,j]);
        close(inp);
end;

function gcd(a,b:longint):longint;
var r: longint;
begin
        repeat
            r := a mod b; 
            a := b;
            b := r;
        until b = 0;
        exit(a);
end;

procedure dp;
var     i,j,x,y:longint;
begin
        for i:=1 to m do
        f[i,n]:=1;
        for j:=n-1 downto 1 do
        for i:=m downto 1 do
        begin
                for y:=j to n do
                for x:=i to m do
                if gcd(a[i,j],a[x,y])>1 then
                begin
                        f[i,j]:=(f[i,j]+f[x,y]);
                        if f[i,j]>=base then dec(f[i,j],base);
                end;
        end;
end;

procedure output;
var     i:longint;
begin
        for i:=1 to m do
        begin
                res:=(res+f[i,1]);
                if res>=base then dec(res,base);
        end;
        write(res);
end;

begin
        input;
        dp;
        output;
end.

Code mẫu của RR

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.

Code mẫu của hieult

#include <cstdio>
//#include <conio.h>
#include <iostream>
#define du 1000000000

long long f[110][110];
int n,m,a[110][110];

int GCD(int a,int b)
{
    int r;
    if(b==0 || a==0) return 0;
    while(b!=0)
    {
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}

int main()
{
   // freopen("NKPATH.in","r",stdin);
    scanf("%d %d",&m,&n);
    for(int i = 1;i<=m;i++)
        for(int j = 1;j<=n;j++)
            scanf("%d",&a[i][j]);
   // printf("%d %d\n",a[1][1],a[1][2]);
    memset(f,0,sizeof(f));
    f[m][n] = 1; for(int i = 1;i<=m;i++) f[i][n] = 1;
    for(int i = n-1;i>=1;i--)
         for(int j = m;j>=1;j--)
         {

               for(int u=n;u>=i;u--)
                    for(int v = m;v>=j;v--)
                    {

                            if(u==i && j==v)
                                 break;
                            if(GCD(a[j][i],a[v][u])>1)
                            {
                                f[j][i] = (f[j][i]+f[v][u])%du;
                             //   printf("%d %d\n",f[j][i],f[v][u]);
                            }
                           // printf("%d\n",GCD(a[j][i],a[v][u]));
                    }
               //printf("%d\n",f[j][i]);
         }
    long long KQ = 0;
    for(int i = 1;i<=m;i++)
        KQ = (KQ+f[i][1])%du;
    printf("%lld",KQ);
  //  getch();
}

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>

using namespace std;

int m, n, a[110][110], f[110][110], res;

int main() {
    scanf("%d%d", &m, &n);
    for(int i=0;i<m;++i) for(int j=0;j<n;++j) scanf("%d", &a[i][j]);
    for(int i=0;i<m;++i) for(int j=0;j<n;++j) {
        for(int u=0;u<=i;++u) for(int v=0;v<=j;++v) if(u+v<i+j && v<n-1) {
            int x = a[i][j], y = a[u][v];
            while(x!=0 && y!=0) {
                if(x>y) x%=y; else y%=x;
            }
            if(x+y>1) f[i][j] = (f[i][j] + f[u][v]) % 1000000000;
        }
        if(j==0) f[i][j] = (1+f[i][j]) % 1000000000;
        if(j==n-1) res = (res+f[i][j]) % 1000000000;
    }
    cout << res << endl;
    //system("pause");
    return 0;
}