Cod sursa(job #462647)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 12 iunie 2010 15:30:14
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<stdio.h>

char bit[2000006];int n,m,v[2000006],pred[2000006];
int sol1,sol2,st,dr,sol,s;

void recur(int mod)
{
	if(!pred[mod])
	{
		printf("1");	
		return ;
	}		
	recur(pred[mod]);
	printf("%d",bit[mod]);
}

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

int main ()
{
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	scanf("%d%d",&n,&m);
	s=(m*n)/cmmdc(m,n);
	v[1]=1;bit[1]=1;viz[1]=1;
	st=dr=1;
	while(st<=dr)
	{
		sol1=v[st]*10;sol1%=s;
		sol2=(sol1+1)%s;
		if(!pred[sol1])
		{
			v[++dr]=sol1;
			pred[sol1]=v[st];
		}	
		if(!pred[sol2])
		{
			v[++dr]=sol2;
			pred[sol2]=v[st];
			bit[sol2]=1;
		}
		st++;
	}
	recur(0);
	return 0;
}