1091.c

来自「平时acm训练时ac的源代码」· C语言 代码 · 共 36 行

#include <stdio.h>
#include <string.h>
#define min(x,y) ( (x)<(y)?(x):(y) )
#define max(x,y) ( (x)>(y)?(x):(y) )

int gcd( int a, int b ){
if ( !a ) return b;
return gcd(b%a,a);
}

int n, b, f;

int ways[51][51][51];

int getways( int d, int g, int last ){
if ( d==n ) return 1;

if ( ways[d][g][last] < 1000000 ) return ways[d][g][last];

int s=0, i,j;
for ( i=last; i<=b; i++ )
	if ( (j=gcd(i,g)) > 1 )
		s=min( 10000, s+getways(d+1,j,i+1) );

return ways[d][g][last]=s;
}

int main( void ){
memset( ways, 66, sizeof(ways) );

scanf( "%d %d", &n, &b );
printf( "%d\n", getways(0,0,2) );

return 0;
}