NKPATH - Đường đi trên lưới
Tác giả: hieult
Ngôn ngữ: C++
#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();
}