Cod sursa(job #129979)

Utilizator savimSerban Andrei Stan savim Data 30 ianuarie 2008 19:42:15
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
int i,j,k,s,p,n,m;
bool rest[2000001],sol[2000001];
int vine[2000001],uc[2000001];
int coada[2000001];
int main()
{


	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);

	scanf("%d %d",&n,&m);
	s=n;p=m;
	while (n%m!=0)
	{
		k=n%m;
		n=m;
		m=k;
	}
	k=(s*p)/m;

	rest[1]=1;coada[1]=1;uc[1]=1;vine[1]=0;p=1;s=1;
	while (!rest[0])
	{
		j=s;
        for (i=p; i<=s; i++)
		{
			if (rest[(coada[i]*10)%k]==0)
			{
				rest[(coada[i]*10)%k]=1;
				s++;
				uc[(coada[i]*10)%k]=0;vine[(coada[i]*10)%k]=coada[i];coada[s]=(coada[i]*10)%k;
			}
			if (rest[0]) break;

			if (rest[(coada[i]*10+1)%k]==0)
			{
				rest[(coada[i]*10+1)%k]=1;
				s++;
				uc[(coada[i]*10+1)%k]=1;vine[(coada[i]*10+1)%k]=coada[i];coada[s]=(coada[i]*10+1)%k;
			}
			if (rest[0]) break;
		}
		p=j;
	}
	p=0;i=0;
	while (vine[i]!=0)
	{
		p++;
		sol[p]=uc[i];
		i=vine[i];
	}
	p++;sol[p]=1;
	for (i=1; i<=p/2; i++)
	{
		s=sol[i];
		sol[i]=sol[p+1-i];
		sol[p+1-i]=s;
	}
	for (i=1; i<=p; i++)
		printf("%d",sol[i]);
	printf("\n");
	return 0;
}