Cod sursa(job #488159)

Utilizator Teodor94Teodor Plop Teodor94 Data 27 septembrie 2010 21:04:56
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<cstdio>

const int N=2000000;

int a,b,incep=1,sfarsit=1,x[N],c[N],y[N],m;
bool p[N];

int cmmdc(int xx,int yy)
{
	int r;
	while (yy)
	{
		r=xx%yy;
		xx=yy;
		yy=r;
	}
	return xx;
}

void citire()
{
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	scanf("%d%d",&a,&b);
	x[sfarsit]=1;
	c[sfarsit]=1;
	p[1]=true;
	m=a*b/cmmdc(a,b);
}

void afis(int xx)
{
	if (xx==0)
		return;
	afis(y[xx]);
	printf("%d",c[xx]);
}

void rez()
{
	int nr,xx;
	while (incep<=sfarsit)
	{
		nr=x[incep];
		for (int i=0;i<=1;++i)
		{
			xx=(nr*10+i)%m;
			if (!p[xx])
			{
				p[xx]=true;
				x[++sfarsit]=xx;
				y[sfarsit]=incep;
				c[sfarsit]=i;
			}
			if (xx==0)
			{
				afis(sfarsit);
				return;
			}
		}
		++incep;
	}
}

int main()
{
	citire();
	rez();
	return 0;
}