Cod sursa(job #113357)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 9 decembrie 2007 18:37:02
Problema Multiplu Scor Ascuns
Compilator cpp Status done
Runda Marime 0.68 kb
#include <stdio.h>
#include <assert.h>

int a,b,par [2000111],cod[2000111],Q,sf;

int cmmdc(int a,int b)
{
	while(a&&b)
		if(a>=b)
			a%=b;
		else
			b%=a;
	return a|b;
}

void Add(int i,int x)
{
	if(!par[i])
		par[i]=x,cod[++sf]=i;
}

void doit(int i)
{
	if(i==1)
	{
		printf("1");
		return ;
	}
	doit(par[i]);
	if((par[i]*10)%a==i)
		printf("0");
	else
		printf("1");
}

int main()
{
	assert(freopen("multiplu.in","r",stdin));
	freopen("multiplu.out","w",stdout);
	assert(scanf("%d %d",&a,&b)==2);
	assert(1<=a*b);
	assert(a*b<=2000000);
	a=a*b/cmmdc(a,b);
	par[1]=1;
	cod[Q=sf=0]=1;
	for(;!par[0];Q++)
		Add((cod[Q]*10)%a,cod[Q]), Add((cod[Q]*10+1)%a,cod[Q]);
	doit(0);
	printf("\n");
	return 0;
}