1426.txt

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

#define debug 0
#define NMAX 200
#define INF 1000000001
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>

int a[NMAX];
int f[NMAX][NMAX];
int prej[NMAX][NMAX],prei[NMAX][NMAX];
int n;
int mod(int k)
{
	memset(a,0,sizeof(a));
	
	a[k]=1;
	int q=0;
	int i;
	for(i=k;i>=1;i--)
	{
		q=(q*10+a[i])%n;
	}
	return q;
}
void solve()
{
	
	memset(f,0,sizeof(f));
	memset(prej,0,sizeof(prej));
	memset(prei,0,sizeof(prei));
	int i,j;
	if(1%n==0)
	{
		printf("1\n");
		return ;
	}
	f[1][1]=1;
	int k;
	for(i=2;i<=NMAX;i++)
	{
		int q=mod(i);
		f[i][q]=1;
		if(q==0)
		{
			f[i][0]=1;
			prei[i][0]=0;
			break;
		}
		for(k=1;k<i;k++)
		{
			for(j=1;j<n;j++)
			{
				if(f[k][j])
				{
					f[i][(q+j)%n]=1;
					prei[i][(q+j)%n]=k;
					prej[i][(q+j)%n]=j;
				}
			}
		}
		if(f[i][0]==1)
			break;
	}
	int m=i;
	printf("1");
	int cpi=prei[i][0];
	int cpj=prej[i][0];
	
	for(--i;i>=1;i--)
	{
		if(i==cpi)
		{
			printf("1");
			cpi=prei[i][cpj];
			cpj=prej[i][cpj];
		}
		else
		{
			printf("0");
		}
	}
	printf("\n");

}
main()
{
#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	
	scanf("%d",&n);
	while(n)
	{
		solve();
		scanf("%d",&n);
	}
#if debug
	fclose(stdin);
	fclose(stdout);
#endif;
	return 1;
}