Cod sursa(job #470760)

Utilizator muscaTudose Vlad-Adrian musca Data 15 iulie 2010 14:15:56
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<stdio.h>
struct codita
{
	
	int c,r,t;
};
codita q[1000001];
char viz[2000001];
int rsp[1000001];
int cmmdc(int a,int b)
{
	int ca,cb,r;
	ca=a;
	cb=b;
	while(cb!=0)
	{	
		r=ca%cb;
		ca=cb;
		cb=r;
	}
	return a*b/ca;
}

int main()
{
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	int a,b,m,num,r1,i,k,p,u,rest,stop,d,d1;
	scanf("%d%d",&a,&b);
	m=cmmdc(a,b);
	p=u=1;
	q[p].c=1; q[p].r=1; q[p].t=0;
	viz[1]=1;
	stop=1;
	while(stop!=0)
	{
		for(i=0;i<=1;i++)
		{
			rest=(q[p].r*10+i)%m;
			if(rest==0)
			{
				q[++u].c=i;
				q[u].r=rest;
				q[u].t=p;
				viz[rest]=1;
				stop=0;
				break;
			}
			else
				if(!viz[rest])
			{
				q[++u].c=i;
				q[u].r=rest;
				q[u].t=p;
				viz[rest]=1;
			}
		}
		++p;
	}
	d=u;
	d1=0;
	while(d!=0)
	{
		rsp[++d1]=q[d].c;
		d=q[d].t;
	}

	for(i=d1;i>=1;i--)
		printf("%d",rsp[i]);
	printf("\n");
	return 0;
}