Cod sursa(job #593305)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 2 iunie 2011 10:51:29
Problema Multiplu Scor 100
Compilator cpp Status done
Runda pregatire_lot_juniori_1 Marime 0.69 kb
#include<stdio.h>

int u[2000001],pred[2000001],c[2000001],x;

int cmmdc(int a, int b)
{
	int c;
	while(b)
	{
		c=a%b;
		a=b;
		b=c;
	}
	return a;
}

void afisare(int p)
{
	if (p!=1)
		afisare(pred[p]);
	printf("%d",u[p]);
}


int main()
{
	int a,b,p,st,dr,i;
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	scanf("%d%d",&a,&b);
	x=(a/cmmdc(a,b))*b;
	for(i=0;i<x;++i)
		u[i]=pred[i]=-1;
	u[1]=1;
	pred[1]=0;
	c[1]=1;
	st=dr=1;
	while (st<=dr)
	{
		p=(c[st]*10)%x;
		if (pred[p]==-1)
		{
			pred[p]=c[st];
			u[p]=0;
			c[++dr]=p;
		}
		
		p=(c[st]*10 +1)%x;
		if (pred[p]==-1)
		{
			pred[p]=c[st];
			u[p]=1;
			c[++dr]=p;
		}
		if (pred[0]!=-1)
			break;
		++st;
	}
	afisare(0);
}