Cod sursa(job #593186)

Utilizator theocmtAxenie Theodor theocmt Data 1 iunie 2011 17:55:50
Problema Multiplu Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<stdio.h>

int a,b,cm,q[1100000],n,x,u[2000001],cif[2000001];

int cmmdc(int x,int y)
{
	int r;
	while(y!=0)
	{
		r = x%y;
		x = y;
		y = r;
	}
	return x;
}

void afis(int p)
{
	if (u[p]!=0)
		afis(u[p]);
	printf("%d", cif[p]);
}

	
int main()
{
	int p;
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	scanf("%d%d",&a,&b);
	
	cm = a*b / cmmdc(a,b);
	q[++n]=1;
	cif[1]=1;
	p=1;
	while (u[0] == 0)
	{
		x=q[p++];
		if(u[x*10 % cm] == 0)
		{
			q[++n] = x*10 % cm;
			cif[q[n]]=0;
			u[q[n]]=q[p-1];
		}
		if (u[0] != 0)
			break;
		if (u[(x*10+1) % cm] == 0)
		{
			q[++n] = (x*10+1) % cm;
			cif[q[n]]=1;
			u[q[n]]=q[p-1];
		}
	}
	
	afis(0);
	return 0;
}