Cod sursa(job #470743)

Utilizator popa.andreeaPopa Andreea Maria popa.andreea Data 15 iulie 2010 13:46:56
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>
struct queue {int c,r,p;}; queue q[100001];
char viz[2000001];
int m,a,n,b,r,i,nr,p,u,rest,stop;
int main()
{
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	scanf("%d%d",&a,&b);
	m=a; n=b;
	while (b!=0)
	{
		r=a%b;
		a=b;
		b=r;
	}
	nr=m*n/a;
	q[1].c=1;
	q[1].r=1;
	q[1].p=0;
	p=u=1;
	viz[1]=1;
	stop=1;
	while (p<=u && stop)
	{
		for (i=0; i<=1; i++)
		{
			rest=(q[p].r*10+i)%nr;
			if (rest==0)
			{
				q[++u].c=i;
				q[u].r=rest;
				q[u].p=p;
				viz[rest]=1;
				stop=0;
				break;
			}
			else
				if (viz[rest]==0)
				{
					q[++u].c=i;
					q[u].r=rest;
					q[u].p=p;
					viz[rest]=1;
				}
		}
		++p;
	}
	p=0;
	while (u!=0)
	{
		p++;
		viz[p]=q[u].c;
		u=q[u].p;
	}
	for (i=1;i<=p;i++)
		printf("%d",viz[i]);
}