Cod sursa(job #532262)

Utilizator gegeadDragos Gegea gegead Data 11 februarie 2011 11:26:01
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<cstdio>
struct queue
{
	bool c;
	int r;
	int t;
};
queue q[1000000];
bool v[1000000],viz[2000001];


int cmmdc(int a,int b)
{
	int r;
	while(b>1)
	{
		r=a%b;
		a=b;
		b=r;
	}
	return r;
}



int cmmmc(int a,int b)
{
	return a*b/cmmdc(a,b);
}



int main()
{
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	int n,a,b,i=1,j,k,c,r;
	scanf("%d%d",&a,&b);
	n=cmmmc(a,b);
	q[1].c=1;
	q[1].r=1;
	q[1].t=0;
	viz[1]=1;
	j=1;
	while(1)
	{
		c=0;
		r=(q[j].r*10+c)%n;
		if(!viz[r])
		{
			q[++i].c=c;
			q[i].t=j;
			q[i].r=r;
			viz[r]=1;
		}
		if(q[i].r==0)
			break;
		c=1;
		r=(q[j].r*10+c)%n;
		if(!viz[r])
		{
			q[++i].c=1; 
			q[i].t=j;
			q[i].r=(q[q[i].t].r*10+q[i].c)%n;
			viz[r]=1;
		}
		if(q[i].r==0)
			break;
		++j;
	}
	k=i;
	for(j=1;;++j)
	{
		v[j]=q[k].c;
		k=q[k].t;
		if(k==0)
			break;
	}
	for(i=1;i<=j;++i)
		printf("%d",v[i]);
	return 0;
}