## Editorial for VOI 06 Bài 6 - Đường đi trên lưới

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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
for i:=1 to m do
for j:=1 to n do
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);
for i:=1 to m do
for j:=1 to n do
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
for i:=1 to m do
for j:=1 to n do

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;
}