1465.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <memory.h>
#include <string.h>


#define MAX 2000
class BigInteger
{
	public:
		int len;
		char cNum[MAX];
		
		BigInteger( int s = 0 )
		{
			len = 0;
			memset( cNum, 0, sizeof( cNum ) );
			while ( s != 0 )
			{
				cNum[ len ++ ] = s % 10;
				s /= 10;
			}	
		}
		
		BigInteger( char* s )
		{
			len = strlen( s );
			memset( cNum, 0, sizeof( cNum ) );
			for (int i=0; i<len; i++)
			{
				cNum[i] = s[len-i-1] - '0';
			}
		}
		
		BigInteger& operator=( int s )
		{
			len = 0;
			memset( cNum, 0, sizeof( cNum ) );
			while ( s != 0 )
			{
				cNum[ len ++ ] = s % 10;
				s /= 10;
			}
			return *this;		
		}
		
		BigInteger operator+(const BigInteger& b )
		{
			BigInteger temp,* c = &temp;
			int mmax = ( len > b.len ) ? len : b.len;
			int up = 0;
			int i = 0;
			for (i=0; i<mmax; i++)
			{
				c->cNum[i] = cNum[i] + b.cNum[i] + up;
				up = c->cNum[i] / 10;
				c->cNum[i] %= 10;
			}
			if ( up != 0 )
			{
				c->cNum[mmax] = up;
				mmax ++;
			}
			c->len = mmax;
			return *c;
		}
		
		BigInteger operator*(const BigInteger& b )
		{
			BigInteger temp,* c = &temp;;
			int mmax = 0;
			int p = 0;
			int up = 0;
			for (int i=0; i<len; i++)
			{
				p = i;
				for (int j=0; j<b.len; j++)
				{
					c->cNum[p] += cNum[i] * b.cNum[j] + up;
					up = c->cNum[p] / 10;
					c->cNum[p] %= 10;
					p ++;
				}
				while ( up != 0 )
				{
					c->cNum[p] += up % 10;
					up /= 10;
					up += c->cNum[p] / 10;
					c->cNum[p] %= 10;
					p ++;
				}
				if ( p > mmax )
					mmax = p;
			}
			for (int k=mmax-1; k>0; k--)
			{
				if ( c->cNum[k] == 0 )
					mmax --;
				else
					break;
			}
			c->len = mmax;
			return *c;
		}
		
		void output( char c = '\0' )
		{
			if ( len == 0 ) putchar('0');

			for (int i=len - 1; i>=0; i--)
			{
				putchar( cNum[i] + '0' );
			}
			putchar( c );
		}
};


////////////////////////////////////////////////////////////////////////////////////


int mem[2][5000], *q1 = mem[0], *q2 = mem[1];
int l1,l2;

int from[5001];
int c[5001];

bool sign[10];

bool check( int a )
{
	while( a && sign[ a%10 ] )
		a /= 10;

	return a==0;
}


int doit( int s )
{
	int i, j, a, b, *temp;

	l1 = 0;

	for( i=1; i<10; i++ )
	if( sign[ s*i%10 ] )
	{
		b = s*i/10;

		from[ b ] = -2;
		c[b] = i;

		if( b == 0 ) return b;

		q1[ l1++ ] = b;
	}

	while( l1 )
	{
		l2 = 0;
		for( i=0; i<10; i++ )
		for( j=0; j<l1; j++ )
		{
			a = q1[j];
			
			if( sign[ (a+s*i)%10 ] )
			{
				b = (a+s*i)/10;

				if( from[b] == -1 )
				{
					from[b] = a;
					c[b] = i;

					if( b==0 )	return b;

				    q2[l2++] = b;
				}
			}
		}

		temp = q1; q1 = q2; q2 = temp;
		a = l1; l1 = l2; l2 = l1;
	}

	return -1;
}

int main()
{
	int i, j, n, m;

	while( scanf( "%d", &n ) == 1 )
	{
		scanf( "%d", &m );

		for( i=0; i<10; i++ )
			sign[i] = false;

		for( i=0; i<m; i++ )
		{
			scanf( "%d", &j );
			sign[j] = true;
		}

		for( i=0; i<=n; i++ )
			from[i] = -1;

		m = doit( n );

		if( m < 0 ) printf( "0\n" );
		else
		{
			BigInteger s(0);
			
			while( m>=0 )
			{
				s = s*BigInteger(10) + BigInteger(n*c[m]);
				m = from[m];
			}
			
			s.output('\n');
		}

	}
	return 0;
}